世 上 没 有 绝 望 的 处 境 只 有 对 处 境 绝 望 的 人

数据结构笔记-线性表及其操作

本博客只为记录，以及对与一些学习线性表的同志提供代码资源20201007

顺序表

/* 线性表及其操作 顺序表 1. 两个有序顺序表成一个有序顺序表 By-Round moon 转载备注说明 */ #include<stdio.h> #include<stdlib.h> #define Init_size 10 #define Increase 10 typedef struct node { int *save; int now_size; int tot_size; } Sqlist; void init(Sqlist*temp) { temp->save=(int*)malloc(sizeof(Sqlist)*Init_size); if(!temp->save) { puts("运行错误!"); exit(0); } temp->now_size=0; temp->tot_size=Init_size; } void add(Sqlist *L,int num) { if(L->now_size==L->tot_size) { L->tot_size+=Increase; int* new_base=(int*)realloc(L->save,sizeof(Sqlist)*L->tot_size); if(!new_base) { puts("运行错误!"); exit(0); } L->save=new_base; } L->save[L->now_size++]=num; } void merge(Sqlist a,Sqlist b,Sqlist *ans) { int now_a=0,now_b=0; while(now_a!=a.now_size&&now_b!=b.now_size) { if(a.save[now_a]<b.save[now_b]) add(ans,a.save[now_a++]); else add(ans,b.save[now_b++]); } while(now_a<a.now_size) add(ans,a.save[now_a++]); while(now_b<b.now_size) add(ans,b.save[now_b++]); } int main() { Sqlist a,b,ans; int n,m,num,i; scanf("%d%d",&n,&m); init(&a); init(&b); init(&ans); for(i=0; i<n; i++) { scanf("%d",&num); add(&a,num); } for(i=0; i<m; i++) { scanf("%d",&num); add(&b,num); } merge(a,b,&ans); for(i=0; i<ans.now_size; i++) { printf("%d",ans.save[i]); if(i==ans.now_size-1) putchar('\n'); else putchar(' '); } return 0; } /* 2 4 1 3 2 4 6 8 */

链表

/* 线性表及其操作 链表 1.创建2.链接3.两个有序链表合并为一个有序链表 By-Round moon 转载备注说明 */ #include<stdio.h> #include<stdlib.h> typedef struct node { struct node *next; int data; } Lnode,*Linklist; Linklist init() { Linklist head=(Linklist)malloc(sizeof(Lnode)); if(!head) { puts("运行错误!"); exit(0); } head->next=NULL; return head; } Linklist add(Linklist now,int num) { Linklist new_note=(Linklist)malloc(sizeof(Lnode)); if(!new_note) { puts("运行错误!"); exit(0); } new_note->data=num; new_note->next=now->next; now->next=new_note; return new_note; } void reverse(Linklist L) { Linklist temp; Linklist now=L->next; Linklist pre=L; while(now!=NULL) { temp=now->next; now->next=pre; pre=now; now=temp; } L->next->next=NULL; L->next=pre; } void display(Linklist L) { Linklist now=L->next; printf("%d",now->data); now=now->next; for(; now!=NULL; now=now->next) printf(" %d",now->data); puts(""); } Linklist merge(Linklist A,Linklist B) { Linklist L=init(),P,now1=A->next,now2=B->next; P=L; while(now1!=NULL&&now2!=NULL) { if(now1->data<now2->data) { P=add(P,now1->data); now1=now1->next; } else { P=add(P,now2->data); now2=now2->next; } } while(now1!=NULL) { P=add(P,now1->data); now1=now1->next; } while(now2!=NULL) { P=add(P,now2->data); now2=now2->next; } return L; } int main() { Linklist A=init(),B=init(),ans; Linklist P1=A,P2=B; int n,m,num,i; printf("请输入A和B链表的长度:\n"); scanf("%d%d",&n,&m); for( i=0; i<n; i++) { scanf("%d",&num); P1=add(P1,num); } for( i=0; i<m; i++) { scanf("%d",&num); P2=add(P2,num); } display(A); display(B); reverse(A); display(A); ans=merge(A,B); display(ans); } /* 4 2 7 5 3 1 2 4 */

By-轮月