2. 线性表 (算法和数据结构笔记)
//起始部分 |
|
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"
#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量*/
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等*/ typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */ |
//输出数据元素的值 |
|
Status visit(ElemType c) { printf("%d ",c); return OK; } |
|
线性表的存储结构需要具备: ①数组[MAXSIZE]; ②线性表的当前长度 | |
|
typedef struct { ElemType data[MAXSIZE]; /* 数组，存储数据元素*/ int length; /* 线性表当前长度*/ }SqList;
|
|
/* 初始化顺序线性表*/ Status InitList(SqList *L) { L->length=0; return OK; } | |
|
①分配基地址→分配失败的处理 ②设置空表长度为; ③将存储容量初始化为LIST_INIT_SIZE
|
|
/* 初始条件：顺序线性表L已存在，≤i≤ListLength(L) */ /* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第个位置的数组是从开始*/ ①说明不能查找的情况: L.length==0 || i<1 || i>L.length; ②取出[i-1]下标的值 |
|
Status GetElem(SqList L,int i,ElemType *e) { if(L.length==0 || i<1 || i>L.length) //length==0的意思是线性的的长度(不是线性表的容量)为, 即线性表中一个元素也没有 return ERROR; *e=L.data[i-1];
return OK; } |
|
/* 初始条件：顺序线性表L已存在*/ /* 操作结果：返回L中第个与e满足相等关系的数据元素的位序。*/ /* 若这样的数据元素不存在，则返回值为*/ ①如果表的length等于零, 或者i大于表的length, 返回; ②遍历表, 找到了就break, 然后返回i+1的值. |
|
int LocateElem(SqList L,ElemType e) { int i; if (L.length==0 || i>=L.length) for(i=0;i<L.length;i++) { if (L.data[i]==e) break; } return i+1; } |
|
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)*/ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加*/ ①如果插入位置不合理，抛出异常； ②如果线性表长度大于等于数组长度，则抛出异常或动态增加容量； ③从最后一个元素开始向前遍历到第i个位置，并且将这些元素都分别向后移动一个位置； ④将要插入元素填入位置i处 ⑤表长加。 |
|
Status ListInsert(SqList *L,int i,ElemType e) { int k; if (L->length==MAXSIZE) /* 顺序线性表已经满*/ return ERROR; if (i<1 || i>L->length+1)/* 当i比第一位置小(例如i=0的情况)或者比最后一位置后一位置还要大时*/ return ERROR;
if (i<=L->length) /* 若插入的数据的位置不在表尾*/ { for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位*/ L->data[k+1]=L->data[k]; /* 第一次循环是将data[2]赋值给data[1] */ } L->data[i-1]=e; /* 将新元素插入*/ L->length++;
return OK; } |
|
/* 初始条件：顺序线性表L已存在，≤i≤ListLength(L) */ /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减*/ ①如果删除位置不合理，抛出异常； ②取出删除元素； ③从删除元素位置开始遍历到最后一个元素位置，并且将它们都分别向前移动一个位置； ④表长减。 |
|
Status ListDelete(SqList *L,int i,ElemType *e) { int k; if (L->length==0) /* 线性表为空*/ return ERROR; if (i<1 || i>L->length) /* 删除位置不正确*/ return ERROR; *e=L->data[i-1]; /* 第i个元素的下标为i-1 */ if (i<L->length) /* 如果删除的数据不在表尾*/ { for(k=i;k<L->length;k++)/* 将删除位置后继元素前移*/ L->data[k-1]=L->data[k]; } L->length--; return OK; } |
|
/* 初始条件：顺序线性表L已存在*/ /* 操作结果：依次对L的每个数据元素输出*/ 思路: 循环调用visit()函数. |
|
Status ListTraverse(SqList L) { int i; for(i=0;i<L.length;i++) visit(L.data[i]); printf("n"); return OK; } |
|
//将所有在线性表Lb中出现但不在La中的数据元素插入到La中 ①声明两个表的长度的变量; ②声明两个表的相同元素的变量; ③求出两个表的长度; ④用插入表的长度进行循环, 在循环体中, 先取出插入表的一个元素, 如果取出的元素不存在于被插入表中, 那么就插入被插入表. |
|
void unionL(SqList *La,SqList Lb) { int La_len,Lb_len,i; ElemType e; /* 声明与La和Lb相同的数据元素e */ La_len=ListLength(*La); /* 求线性表的长度*/ Lb_len=ListLength(Lb); for (i=1;i<=Lb_len;i++) { GetElem(Lb,i,&e); /* 取Lb中第i个数据元素赋给e */ if (!LocateElem(*La,e)) //相当于if(LocateElem(*La,e)==0) ListInsert(La,++La_len,e); //插入 } } |
//主函数 |
|
int main() {
SqList L; ElemType e; Status i; int j,k; i=InitList(&L); printf("初始化L后：L.length=%dn",L.length); for(j=1;j<=5;j++) i=ListInsert(&L,1,j); printf("在L的表头依次插入～后：L.data="); ListTraverse(L);
printf("L.length=%d n",L.length); i=ListEmpty(L); printf("L是否空：i=%d(1:是0:否)n",i);
i=ClearList(&L); printf("清空L后：L.length=%dn",L.length); i=ListEmpty(L); printf("L是否空：i=%d(1:是0:否)n",i);
for(j=1;j<=10;j++) ListInsert(&L,j,j); printf("在L的表尾依次插入～后：L.data="); ListTraverse(L);
printf("L.length=%d n",L.length);
ListInsert(&L,1,0); printf("在L的表头插入后：L.data="); ListTraverse(L); printf("L.length=%d n",L.length);
GetElem(L,5,&e); printf("第个元素的值为：%dn",e); for(j=3;j<=4;j++) { k=LocateElem(L,j); if(k) printf("第%d个元素的值为%dn",k,j); else printf("没有值为%d的元素n",j); }
k=ListLength(L); /* k为表长*/ for(j=k+1;j>=k;j--) { i=ListDelete(&L,j,&e); /* 删除第j个数据*/ if(i==ERROR) printf("删除第%d个数据失败n",j); else printf("删除第%d个的元素值为：%dn",j,e); } printf("依次输出L的元素："); ListTraverse(L);
j=5; ListDelete(&L,j,&e); /* 删除第个数据*/ printf("删除第%d个的元素值为：%dn",j,e);
printf("依次输出L的元素："); ListTraverse(L);
//构造一个有个数的Lb SqList Lb; i=InitList(&Lb); for(j=6;j<=15;j++) i=ListInsert(&Lb,1,j);
unionL(&L,Lb);
printf("依次输出合并了Lb的L的元素："); ListTraverse(L);
return 0; }
|
//起始部分 |
|
#include "stdio.h" #include "string.h" #include "ctype.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"
#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量*/ typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等*/ typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */ |
//输出数据元素的值 |
|
Status visit(ElemType c) { printf("%d ",c); return OK; } |
|
//单链表的存储结构: ①数据域; ②指针域 |
|
typedef struct Node { ElemType data; struct Node *next; //next是Node结构体指针类型的 }Node;
typedef struct Node *LinkList; /* LinkList表示struct Node* */ |
|
/* 初始化单链表*/ ①将一个sizeof(Node)的空间分配给*L; ②如果分配失败, 返回异常; ③将指针域设置为NULL; ④返回OK, 即. |
|
Status InitList(LinkList *L) { *L=(LinkList)malloc(sizeof(Node)); /* 分配一个节点的空间, 产生头结点,并使L指向此头结点*/ //L是struct Node** 类型的, 即L是一个二级指针, *L表示取L指针指向的变量的内容--一个struct Node*类型的指针 if(!(*L)) /* 存储分配失败, 即if((*L)=0) */ return ERROR; (*L)->next=NULL; /* 指针域为空*/
return OK; } |
/* 初始条件：单链表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */ |
|
Status ListEmpty(LinkList L) { if(L->next) return FALSE; else return TRUE; } |
|
/* 初始条件：单链表L已存在。操作结果：将L重置为空表(清空, 不是销毁)*/
注意: 总之, 我们要保留头结点, 然后将后面的结点一一删除, 最后将头结点的指针域赋值为空. 在此之后, 这个链表还存在，可以继续使用. | |
|
Status ClearList(LinkList *L) { LinkList p,q; p=(*L)->next; /* p指向第一个结点*/ while(p) /* 没到表尾*/ { q=p->next; //q用来临时记录p的后继结点 free(p); p=q; } (*L)->next=NULL; /* 头结点指针域为空*/ return OK; }
|
|
/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数*/ ①声明一个变量i用来计数; ②声明一个LinkList型的变量p, 并指向单链表的第一个结点, 即L->next; ③当p!=0时, 进入循环, 在循环体内, 先将i加, 然后将指针p指向p的后继结点, 如此继续循环; ④返回i. |
|
int ListLength(LinkList L) { int i=0; LinkList p=L->next; /* p指向第一个结点*/ while(p) { i++; p=p->next; } return i; } |
|
/* 初始条件：单链表L已存在，≤i≤ListLength(L) */ /* 操作结果：用e返回L中第i个数据元素的值*/ ①声明一个LinklList型指针p指向链表的第一个结点(不是头结点); ②声明变量j作为计数器从开始； ②当j<i时，就遍历链表--让p指针不断指向下一结点，j不断累加1； ③若到链表末尾时p为空，则说明第i个结点不存在； ④否则查找成功，返回结点p的数据。 |
|
Status GetElem(LinkList L,int i,ElemType *e) { int j= 1 /* j为计数器*/ LinkList p; /* 声明一结点p */ p = L->next; /* 让p指向链表L的第一个结点*/ while (p && j<i) /* p不为空或者计数器j还没有等于i时，循环继续*/ { p = p->next; /* 让p指向下一个结点*/ ++j; } if ( !p || j>i ) return ERROR; /* 第i个元素不存在*/ *e = p->data; /* 取第i个元素的数据*/ return OK; } |
|
/* 初始条件：顺序线性表L已存在*/ /* 操作结果：返回L中第个与e满足相等关系的数据元素的位序。*/ /* 若这样的数据元素不存在，则返回值为*/ ①声明一个LinkList型指针p指向链表第一个结点; ②声明变量i作为计数器从0开始； ③当p!=0时,先将i加, 如果此时p的数据域等于e,那么就返回i, 否则将p指针指向下一结点; ④退出循环后返回. |
|
int LocateElem(LinkList L,ElemType e) { LinkList p=L->next; int i=0; //i是计数器 while(p) { i++; if(p->data==e) /* 找到这样的数据元素*/ return i; p=p->next; }
return 0; } |
|
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L) */ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加*/ ①声明两个LinkList型指针p和s, p指向链表第一个结点(不是首节点); ②声明变量j作为计数器从1开始; ③当p不为空且j<i时，就遍历链表----让p指针不断指向下一结点，j不断累加1; ④当p==0或j>i时,说明第i个元素不存在, 返回ERROR; ⑤分配一个LinkList型的新节点s; ⑥将e赋值给s结点的数据域; ⑦把s结点的指针域指向p的后继结点(把p的后继结点变成s的后继结点); ⑧把p结点的指针域指向s结点(把s结点变成p的后继结点) ⑨返回OK, 即1. 注: 因为这里没有指向p结点的后继结点的指针, 所以用p->next来代表p的后继结点. |
|
Status ListInsert(LinkList *L,int i,ElemType e) {
LinkList p,s; int j; p = *L; j = 1; while (p && j < i) /* 寻找第i个结点*/ { p = p->next; ++j; } if (!p || j > i) return ERROR; /* 第i个元素不存在*/ s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */ s->data = e; s->next = p->next; /* 将p的后继结点赋值给s的后继 */ p->next = s; /* 将s赋值给p的后继*/ return OK; } |
|
/* 初始条件：顺序线性表L已存在，≤i≤ListLength(L) */ /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减*/ ①声明两个LinkList型指针p和q, p指向链表的首节点(不是链表的第一个结点), q在下面用来代表欲删除的结点; ②声明变量j作为计数器从开始; ③当p->next不为空,且j<i时，就遍历链表-- 让p指针向后移动，不断指向下一个结点, j不断累加; ④如果p->next为空, 或j>i时,说明第i个元素不存在, 返回ERROR; ⑤否则说明查找到了与删除的结点, 将q指向p的后继结点(欲删除的结点), 即q=q->next; ⑥将p结点的指针域指向q的后继结点; ⑦将q结点的指针域赋值给*e, 然后释放q; ⑧返回OK. 注: 我们这里只有q和p指针分别指向欲删除的结点和欲删除结点前的结点, 至于欲删除节点后的结点用q->next来表示. |
|
Status ListDelete(LinkList *L,int i,ElemType *e) {
LinkList p,q; p = *L; int j= 1; while (p->next && j < i) /* 遍历寻找第i个元素*/ { p = p->next; ++j; } if (!(p->next) || j > i) return ERROR; /* 第i个元素不存在*/ q = p->next; p->next = q->next; /* 将q的后继赋值给p的后继*/ *e = q->data; /* 将q结点中的数据给e */ free(q); /* 让系统回收此结点，释放内存*/ return OK; } |
|
/* 初始条件：顺序线性表L已存在*/ /* 操作结果：依次对L的每个数据元素输出*/ ①声明一个LinkList型的指针变量p指向单链表的第一个结点(不是头结点); ②当指针p!=0时, 首先读取p指向的数据节点的数据域, 然后将p指针指向下一个结点(p->next), 如此继续循环. |
|
Status ListTraverse(LinkList L) { LinkList p=L->next; while(p) { visit(p->data); p=p->next; } printf("n"); return OK; } |
|
/* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）*/ ①声明一个LinkList型的指针p和计数器变量i; ②初始化随机数种子; ③分配sizeof(Node)大小的内存(Linklist型), 并赋值给*L, 从而初始化了一个空链表L; ④让L的头结点的指针指向NULL，即建立一个带头结点的单链表； ⑤循环： 生成一新结点赋值给p； 随机生成一个数字并赋值给p的数据域p->data； 将p插入到头结点与前一新结点之间。
注意: LinkList p; //p是struct Node*类型的 LinkList *L; //L是struct Node**类型的, 所以*L是struct Node*类型的 和单链表相关的函数的形参有可能是LinkList型的或LinkList*的, 要表示单链表的头结点可分别用L或*L, 要表示单链表的第一个结点(不是头结点)可分别用L->next或(*L)->next;
|
|
void CreateListHead(LinkList *L, int n) { LinkList p; int i; srand(time(0)); /* 初始化随机数种子*/ *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; /* 先建立一个带头结点的单链表*/ for (i=0; i<n; i++) { p = (LinkList)malloc(sizeof(Node)); /* 生成新结点*/ p->data = rand()%100+1; /* 随机生成以内的数字*/ p->next = (*L)->next; (*L)->next = p; /* 插入到表头*/ } } |
|
/* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）*/ ① |
|
void CreateListTail(LinkList *L, int n) { LinkList p,r; int i; srand(time(0)); /* 初始化随机数种子*/ *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表*/ r=*L; /* r为指向尾部的结点*/ for (i=0; i<n; i++) { p = (Node *)malloc(sizeof(Node)); /* 生成新结点*/ p->data = rand()%100+1; /* 随机生成以内的数字*/ r->next=p; /* 将表尾终端结点的指针指向新结点*/ r = p; /* 将当前的新结点定义为表尾终端结点*/ } r->next = NULL; /* 表示当前链表结束*/ } |
|
int main() { LinkList L; ElemType e; Status i; int j,k; i=InitList(&L); printf("初始化L后：ListLength(L)=%dn",ListLength(L)); for(j=1;j<=5;j++) i=ListInsert(&L,1,j); printf("在L的表头依次插入～后：L.data="); ListTraverse(L);
printf("ListLength(L)=%d n",ListLength(L)); i=ListEmpty(L); printf("L是否空：i=%d(1:是0:否)n",i);
i=ClearList(&L); printf("清空L后：ListLength(L)=%dn",ListLength(L)); i=ListEmpty(L); printf("L是否空：i=%d(1:是0:否)n",i);
for(j=1;j<=10;j++) ListInsert(&L,j,j); printf("在L的表尾依次插入～后：L.data="); ListTraverse(L);
printf("ListLength(L)=%d n",ListLength(L));
ListInsert(&L,1,0); printf("在L的表头插入后：L.data="); ListTraverse(L); printf("ListLength(L)=%d n",ListLength(L));
GetElem(L,5,&e); printf("第个元素的值为：%dn",e); for(j=3;j<=4;j++) { k=LocateElem(L,j); if(k) printf("第%d个元素的值为%dn",k,j); else printf("没有值为%d的元素n",j); }
k=ListLength(L); /* k为表长*/ for(j=k+1;j>=k;j--) { i=ListDelete(&L,j,&e); /* 删除第j个数据*/ if(i==ERROR) printf("删除第%d个数据失败n",j); else printf("删除第%d个的元素值为：%dn",j,e); } printf("依次输出L的元素："); ListTraverse(L);
j=5; ListDelete(&L,j,&e); /* 删除第个数据*/ printf("删除第%d个的元素值为：%dn",j,e);
printf("依次输出L的元素："); ListTraverse(L);
i=ClearList(&L); printf("n清空L后：ListLength(L)=%dn",ListLength(L)); CreateListHead(&L,20); printf("整体创建L的元素(头插法)："); ListTraverse(L);
i=ClearList(&L); printf("n删除L后：ListLength(L)=%dn",ListLength(L)); CreateListTail(&L,20); printf("整体创建L的元素(尾插法)："); ListTraverse(L);
return 0; } |
|
//静态链表和单链表的对应关系如下图:
注：①静态链表以next==-1作为其结束的标志。 ②静态链表的插入、删除操作与动态链表相同，只需要修改指针，而不需要移动元素。 ③总体来说，静态链表没有单链表使用起来方便，但是在一些不支持指针的高级语言（如Basic）中，这又是一种非常巧妙的设计方法。 |
|
//静态链表结构类型的描述 #define MaxSize 50 //静态链表的最大长度 typedef struct{ //静态链表结构类型的定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标; 有的资料用的是 }SLinkList[MaxSize]; |
|
//一. 循环链表的案例 /* 有两个循环链表A和B, 其尾指针分别是rearA和rearB, 它们分别指向表A和表B的头结点*/ /* 先要求合并循环列表A和B */ ①声明两个LinkList型的变量p和q; ②将指针p指向链表A的头结点; ③将rearA结点的指针域指向rearB的第一个结点; ④释放B表的头结点 ⑤将rearB的指针域指向链表A的头结点 |
|
LinkList Connect(LinkList A,LinkList B) {//假设A，B为非空循环链表的尾指针 LinkList p; LinkList p=A->next;//将指针p指向链表A的头结点 A->next=B->next->next;//将rearA结点的指针域指向rearB的第一个结点 free(B->next);//释放B表的头结点 B->next=p;//将rearB的指针域指向链表A的头结点 return B;//返回新循环链表的尾指针 } |
|
/* 线性表的双向链表存储结构*/ 包括: 数据域, 前驱指针域, 后继指针域 |
|
typedef struct DulNode { ElemType data; struct DuLNode *prior; /* 直接前驱指针*/ struct DuLNode *next; /* 直接后继指针*/ } DulNode, *DuLinkList; |
|
//双向列表的插入
|
|
/* 把p赋值给s的前驱，如图中①*/ s->prior = p; /* 把p->next赋值给s的后继，如图中②*/ s->next = p->next; /* 把s赋值给p->next的前驱，如图中③*/ p->next->prior = s; /* 把s赋值给p的后继，如图中④*/ p->next = s; |
|
//双向列表的删除 |
|
/* 把p->next赋值给p->prior的后继，如图中①*/ p->prior->next = p->next; /* 把p->prior赋值给p->next的前驱，如图中②*/ p->next->prior = p->prior; /* 释放结点*/ free(p); |