数据结构基础（一）

线性表

线性顺序表

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 50 typedef 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;