数据结构总复习

文章目录 线性表动态分配的顺序存储结构链式存储

线性表 动态分配的顺序存储结构

通过分析代码，我们发现，要注意什么：

要分清你的下标Insert 函数是可以用来没有元素的时候，增加元素的Init(或者Create )函数一般只用来分配空间等的初始化 //动态分配空间的顺序存储结构的线性表 #include<stdio.h> #include<stdlib.h> #define Linitesize 100 #define Laddsize 10 #define OK 1 #define error 0 typedef int Status; typedef int Elemtype; typedef struct{ Elemtype * elem; int length; int listsize; }SqList; void Show(SqList L) { int i; for(i=0;i<L.length ;i++) printf("%d ",L.elem[i]); printf("\n"); return ; } Status Create(SqList &L) { L.elem = (Elemtype *)malloc(Linitesize*sizeof(Elemtype)); if(!(L.elem )) return error; L.length = 0; L.listsize = Linitesize; return OK; } //在第i个元素之前插入 ，从1开始计数，就是下标为i Status Insert(SqList &L,int i,Elemtype e) { int j; if(i<1||i>L.length+1 ) return error; if(L.length>=L.listsize) { L.elem =(Elemtype *)realloc(L.elem ,(L.listsize + Laddsize)*sizeof(Elemtype)); if(!(L.elem )) return error; L.listsize = L.listsize + Laddsize; } for(j=L.length-1 ;j>=i-1;j--) L.elem[j+1] = L.elem[j]; L.elem[i-1] = e; L.length ++; return OK; } //i为你想要删除的第几个元素 Status Delete(SqList &L,int i,Elemtype &e) { int j; if(i<1||i>L.length ) return error; e = L.elem[i-1]; for(j=i-1;j<L.length-1;j++) L.elem[j] = L.elem[j+1]; L.length --; return OK; } int main() { int i,j; Elemtype e; SqList L; Create(L); for(i=1;i<=5;i++) Insert(L,i,i*i); printf("输出具体数据:\n"); Show(L); printf("请输入你想要删除第几个元素:\n"); scanf("%d",&j); Delete(L,j,e); printf("删除的数据是:%d \n",e); Show(L); return 0; }

考点

两个有序递增的顺序表的合并

关键点，可以学到什么，就是分别用pa,pb,pc,来记录首地址，一句话，就是用辅助变量来方便操作

void Merge(Sqlist la,Sqlist lb,Sqlist &lc) //目标，将原本有序递增的la,pb顺序表整合到lc ,lc认为有序递增的 { pa = la.elem; pb = la.elem; lc.listsize = lc.length = la.length + lb.length; pc =lc.elem = (ElemType *)malloc(lc.listsize*(sizeof(ElemType))); if(!lc.elem) exit OVERFLOW; pa_last = pa + la.length-1; pb_last = pb + lb.length-1; while(pa<=pa_last&&pb<=pb_last) { if(*pa<*pb) *pc++ = *pa++; else *pc++ = *pb++; } while(pa<=pa_last) *pc++ = *pa++; while(pb<=pb_last) *pc++ = *pb++; }

顺序表优点与缺点：

优点：可以随便进行数据的插入与删除优点：占据较少的空间 缺点：需要连续的一串地址缺点：在插入与删除时，要移动大量的元素 链式存储