线性表线性顺序表

1、线性表的数据操作

2、使用定义的函数实现两个集合LA和LB的合并：

void unionList(List LA,List LB,List &LC){ int lena,i; ElemType e; InitList(LC); //将LA的所有元素插入到LC中 for (i=1;i<=ListLength(LA);i++) { GetElem(LA,i,e); ListInsert(LC,i,e); } lena=ListLength(LA); //将LB的所有元素插入到LC for(i=1;i<ListLength(LB);i++) { GetElem(LB,i,e); if (!LocateElem(LA,e)) ListInsert(LC,++lena,e); } }

3、顺序表存储类型的定义

# define MaxSize 50typedef struct{ ElemType date[MaxSize]; int length;}SqList;

4、创建线性表

void CreateList(Sqlist *&L,ElemType a[],int n){ int i; L=(SqList *)malloc(sizeof(SqList)); // malloc 相当于new,分配SqList大小的内存空间，指向SqLost的指针，并将地址赋值给L for (i=0;i<n;i++) L->data[i]=a[i]; L->length=n; }

5、初始化线性表

void InitList(SqList *&L) // 应用指针{ L=(SqList *)malloc(sizeof(SqList)); L->length=0; // 初始化线性表的长度 }

6、销毁线性表

void DestroyList(SqlList *&L){ free(L); }

7、判断线性表是否为空

bool ListEmpty(SqList *L){ return(L->length==0);}

8、求线性表的长度

int ListLength(SqList *L){ return(L->length); }

9、输出线性表

void DispList(SqList *L){ int i; if (ListEmpty(L)) return; for (i=0;i<L->length;i++) printf("%d ",L->data[i]); printf("\n");}

10、求某个数据元素的值，返回L中的第i个元素的值，并存入e中，1<=i<=ListLength(L)

bool GetElem(SqList *L,int i,ElemType &e){ if (i<1||i>L->length) return false; e=L->data[i-1]; return true;}

11、按元素值查找

int LocateElem(L,e){ int i = 0; while (i<L->length && L->data[i]!=e) i++; if (i>=L->length) return 0; else return i+1;}

12、插入元素

bool ListInsert(SqList *&L,int i,ElemType e){ int j; if (i<1||i>L->length+1) return false; i--; for (j=L->length;j>i;j--) L->data[j]=L->data[j-1]; L->data[i]=e; L->length++; return true; }

13、删除元素

bool ListDelete(SqList *&L,int i,ElemType &e){ int j; if (i<1||i>L->length) return false; i--; e=L->data[i]; for(j=i;j<L->length-1;j++) L->data[j]=L->data[j+1]; L->length--; return true; }线性链表

1、单链表的存储结构的定义

typedef struct LNode // 定义单链表节点类型{ ElemType data; //数据域 struct LNode *next; //指针域，指向后继节点 递归结构 }LinkList;

2、单链表的头插法：

void CreateListF(LinkList *&L,ElemType a[],int n){ LinkList *S; int i; L=(LinkList *)malloc(sizeof(LinkList)); L->next=NULL; for(i=0;i<n;i++) { S=(LinkList *)malloc(sizeof(LinkList)); S->data=a[i]; S->next=L->next; L->next=S; } }

3、单链表尾插法

void CreateListR(LinkList *&L,ElemType a[],int n){ LinkList *s,*r; int i; L=(LinkList *)malloc(sizeof(LinkList)); r=L; for(i=0;i<n;i++) { s=(LinkList *)malloc(sizeof(LinkList)); s->data=a[i]; r->next=s; r=s; } r->next=NULL;}

4、单链表的基本操作

5、初始化线性表

void InitList(LinkList *&L){ L=(LinkList *)malloc(sizeof(LinkList)); L->next=NULL;}

6、销毁线性表

void DestroyList(LinkList *&L){ LinkList *pre=L,*p=L->next; while (p=NULL) { free(pre); pre=p; p=pre->next; } free(pre); }

7、判断表为空

bool ListEmpty(LinkList *L){ return(L->next==NULL);}

8、求线性表的ListLength(L)

int ListLength(LinkList *L) { int n=0; LinkList *p=L; while (p->next!=NULL) { n++; p=p->next; } return(n); }

9、输出线性表：

void DisList(LinkList *L){ LinkList *p=L->next; while(p!=NULL) { printf("%d",p->data); p=p->next; } printf("\n") }

10、查找某个元素

bool GetElem(LinkList *L,int i,ElemType &e) { int j=0; LinkList *p=L; while (j<i&&p!=NULL) { j++; p=p->next; } if (p==NULL) return false; else { e=p->data; return true; } }

11、 按元素查找，返回元素的位置

int LocateElem(LinkList *L,ElemType e) { int i=1; LinkList *p=L->next; while (p!=NULL&& p->data!=e) { p=p->next; i++; } if (p==NULL) return 0; else return i; }

12、插入数据元素：

bool ListInsert(LinkList *&L,int i,ElemType e){ int j=0; LinkList *p=L,*S; while (j<i-1 && p!=NULL){ j++; p=p->next; } if (p==NULL) return false; else{ S=LinkList *)malloc(sizeof(LinkList)); S->data=e; S->next=p->next; p->next=S; return true; } }

13、删除数据元素

bool ListDelete(LinkList *&L,int i,ElemType &e) { int j=0; LinkList *p=L,*q; while(j<i-1 && p!=NULL){ j++; p=p->next; } if (p==NULL) return false; else{ q=p->next; if(q=NULL) return false; e=q->data; p->next=q->next; free(q); return true; } }双链表

1、双向链表的定义和存储结构

typedef struct DNode { ElemType data; struct DNode *prior; struct DNode *next; }DLinkList;

2、头插法建立双链表

{ DLinkList *S; int i; L=(DLinkList *)malloc(sizeof(DLinkList)); L->prior=L->next=NULL; for(i=0;i<n;i++) { S=(DLinkList *)malloc(sizeof(DLinkList)); S->data=a[i]; S->next=L->next; if(L->next!=NULL) L->next->prior=S; L->next=S; S->prior=L; } }

3、尾插法建立双链表

void CreateListR(DLinkList *&L,ElemType a[],int n) { DLinkList *s,*r; int i; L=(DLinkList *)malloc(sizeof(DLinkList)); r=L; for (i=0;i<n;i++) { s=(DLinkList *)malloc(sizeof(DLinkList)); s->data=a[i]; r->next=s; s->prior=r; r=s; } r->next=NULL; }

4、插入节点：

bool ListInsert(DLinkList *&L,int i,ElemType e) { int j=0; DLinkList *p=L,*s; while(j<i-1 && p!=NULL) { j++; p=p->next; } if (p=NULL) return false; else { s=(DLink *)malloc(sizeof(DLinkList)); s->data=e; s->next=p->next; if (p->next!=NULL) P->next->prior=s; s->prior=p; p->next=s; return true; } }

5、双链表删除节点

bool ListDelete(DLinkList *&L,int i,ElemType &e) { int j=0; DLinkList *p=L, *q; while (j<i-1 && p!=NULL) { j++; p=p->next; } if (p==NULL) return false; else { q=p->next; if (q==NULL) return false; e=q->data; p->next=q->next; if (p->next!=NULL) p->next->prior=p; free(q); return true; } }有序表的操作

1、有序顺序表的插入操作：

void ListInsert(SqList *&L,ElemType e) { int i =0,j; while (i<L->length && L->data[i]<e) i++; for (j=ListLength(L);j>i;j--) L->data[j]=L->data[j-1]; L->data[i]=e; L->length++; }

2、有序链表的插入操作：

void ListInsert(LinkList *&L,ElemType e) { LinkList *pre=L, *p; while (pre->next!=NULL && pre->next->data < e) pre=pre->next; p=(LinkList *)malloc(sizeof(LinkList)); p->data=e; p->next=pre->next; pre->next=p; }

3、采用顺序表存放有序表时的归并算法（将顺序表LA和LB中的元素插入到LC中形成一个新的顺序表）：

void UnionList(SqList *LA,SqList *LB,SqList *&LC){ int i=0,j=0,k=0; LC=(SqList *)malloc(sizeof(SqList)); // LA和LB均未达到末尾时，择其小加入LC while(i<LA->length && j<LB->length) { if(LA->data[i]<LB->data[j]) { LC->data[k]=LA->data[i]; i++; } else { LC->data[k]=LB->data[j]; j++; } k++; } // LA 尚未扫描完，将其余元素插入LC中 while(i<LA->length) { LC->data[k]=LA->data[i]; i++; k++; } while(j<LB->length) { LC->data[k]=LB->data[j]; j++; k++; }}

4、采用单链表存放有序表时的归并算法（将有序链表LA和LB中的元素插入到LC中形成一个新的有序链表）：

void UnionList1(LinkList *LA,LinkList *LB,LinkList *&LC){ LinkList *pa=LA->next, *pb=LB->next, *r,*s; LC=(LinkList *)malloc(sizeof(LinkList)); r=LC; // LA 和 LB 均未达到末尾时，择其小优先尾插 while(pa!=NULL && pb!=NULL) { S=(LinkList *)malloc(sizeof(LinkList)); if(pa->data<pb->data) { s->data=pa->data; pa=pa->next; } else { s->data=pb->data; pb=pb->next; } r->next=s; r=s; } // LA 未达到末尾，复制LA中所有结点 while(pa!=NULL) { s=(LinkList *)malloc(sizeof(LinkList)); s->data=pa->data; r->next=s; r=s; pa=pa->next; } // LB 未达到末尾，复制LA中所有结点 while(pb!=NULL) { s=(LinkList *)malloc(sizeof(LinkList)); s->data=pb->data; r->next=s; r=s; pb=pb->next; } }栈和队列

1、栈的判定：

栈空： top = -1栈满： top = MaxSize-1进栈e操作：top ++ ; 将e放在top处退栈操作：从top处取出元素e; top --;

2、初始化一个空栈s,实际上是将栈顶指针指向-1即可。

// 定义一个顺序栈typedef struct{ ElemType data[MaxSize]; int top;}SqStack;void InitStack(SqStack *&s){ s=(SqStack *)malloc(sizeof(SqStack)); // 申请内存空间 s->top=-1;}

3、释放栈s占用的空间，销毁栈：

void DestoryStack(SqStack *&s){ free(s);}

4、进栈操作push(&s,e)

条件：在栈不满时，可以进栈操作：将栈指针+1在该位置上插入元素e

bool Push(SqStack *&s,ElemType e){ if （s->top==MaxSize-1） return false; // 栈满 s->top++ s->data[s->top]=e; return true;}

5、Pop(&s,&e)出栈

条件： 栈不为空操作：栈顶元素赋值给e指针减1

bool Pop(SqStack *&s,ElemType &e){ if (s->top==-1) return false; e=s->data[s->top]; s->top--; return true;}

6、用栈判断对称串算法

bool summetry(ElemType str[]){ int i; ElemType e; SqStack *st; InitStack(st); // 将所有元素进栈 for (i=0;str[i]!='\0';i++) Push(str,str[i]); // 出栈的字符与从左向右读取的字符串比较 for(i=0;str[i]!='\0';i++) { Pop(st,e); if(str[i]!=e) { DestroyStack(st); return false; } }DestroyStack(st);return true;}栈的链式存储结构

1、栈的链式存储

* 采用单链表： 头结点后保存栈顶 * 优点：不存在栈满上溢的情况 * 栈空条件： s->next=NULL

定义：

typedef struct linknode{ ElemType data; struct linknode *next; }LiStack;

2、建立一个空栈

void InitStack(LiStack *&s){ s=(LiStack *)malloc(sizeof(LiStack)); s->next=NULL; }

3、释放栈的全部占用空间

void DetroyStack(LiStack *&s) { LiStack *p=s, *q=s->next; while (q!=NULL) { free(p); p=q; q=p->next; } free(p); }

4、判断栈是否为空

bool StackEmpty(LiStack *S) { return(s->next==NULL); }

5、进栈

void Push(LiStack *&s,ElemType e) { LiStack *p; p=(LiStack *)malloc(sizeof(LiStack)); p->data=e; p->next=s->next; s->next=p; }

6、 出栈

bool Pop(LiStack *&s, ElemType &e) { LiStack *p; if (s->next==NULL) return false; p=s->next; e=p->data; s->next=p->next; free(p); return true; }

7、取栈顶元素

bool GetTop(LiStack *s,ElemType &e) { if (s->next==NULL) return false; e=s->next->data; return true; }队列

队列的数据操作：

InitQueue(&q): 初始化队列，构造一个新队列DestroyQueue(&q): 销毁队列。QueueEmpty(q):判断队列是否为空enQueue(&q,e): 进队列。将元素e进队，作为队尾元素。deQueue(&q,&e): 出队列。

队列的存储结构：

数据元素data : 元素具有同一类型ElemType.最多Maxsize当前队首： front当前队尾：rear

定义结构：

typedef struct{ ElemType data[MaxSize]; int front,rear; //队首和队尾指针 } SqQueue;

1、顺序队的特性

队空条件： front = rear队满条件： rear = MaxSize - 1元素e进队： rear ++; data[rear]=e;元素e出队： front ++; e=data[front];rear指向队尾元素front指向队头元素的前一个位置

2、初始化队列

void InitQueue(SqQueue *&q) { q=(SqQueue *)malloc(sizeof(SqQueue)); q->front=q->rear=-1; }

3、释放队列q所占的存储空间

void DestroyQueue(SqQueue *&q) { free(q); }

4、判断队列是否为空QueueEmpty

bool QueueEmpty(SqQueue *q){ return(q->front==q->rear);}

5、进队列

bool enQueue(SqQueue *&q,ElemType e){ if (q->rear==MaxSize-1) return false; q->rear++ q->data[q->rear]=e; return true;}

6、出队列

bool deQueue(SqQueue *&q,ElemType &e){ if (q->front==q->rear) return false; q->front++; e=q->data[q->front]; return true;}

提示：顺序队列在满队数据取完后，在队空的情况下会出现front==rear&& rear = MaxSize - 1的情况，而出现这种情况后，无法再插入数据，这就需要使用环形队列。

环形队列队空条件： front=rear队满条件：（rear+1）%MaxSize=front进队e操作： rear=(rear+1)%MaxSize; 将e放在rear处处队操作：front=(front+1)%MaxSize; 取出front处元素e;