数据结构C语言版算法大全
- 格式：doc
- 大小：330.91 KB
- 文档页数：25
1) 插入操作
在顺序表L的第i (1<=L.length+1)个位置插入新元素e。如果i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。
1. bool ListInsert(SqList &L, int i, ElemType e){
2. //本算法实现将元素e插入到顺序表L中第i个位置
3. if ( i<1 || i>L.length+1 )
4. return false; // 判断i的范围是否有效
5. if(L.length>=MaxSize)
6. return false; // 当前存储空间已满，不能插入
7. for (int j =L.length; j >=i; j--) // 将第i个位置及之后的元素后移
8. L.data[j]=L.data[j-l];
9. L.data[i-1]=e; //在位置i处放入e
10. L.length++; //线性表长度加1
11. return true;
12. }
2) 删除操作
删除顺序表L中第i (1<=i<=L.length)个位置的元素，成功则返回true,否则返回false，并将被删除的元素用引用变量e返回。
复制纯文本新窗口
1. bool ListDelete(SqList &L,int i, int &e){
2. //本算法实现删除顺序表L中第i个位置的元素
3. if(i<1 || i>L.length)
4. return false; // 判断i的范围是否有效
5. e=L.data[i-1] ; // 将被删除的元素赋值给e
6. for (int j=i; j
7. L.data[j-1]=L.data[j]; 8. L.length--; //线性表长度减1
9. return true;
10. }
3) 按值查找（顺序查找）
在顺序表L中查找第一个元素值等于e的元素，并返回其下标。
1. int LocateElem(SqList L, ElemType e){
2. //本算法实现查找顺序表中值为e的元素，如果查找成功，返回元素位序，否则返回0
3. int i;
4. for(i=0;i
5. if(L.data[i]==e)
6. return i+1; // 下标为i的元素值等于e，返回其位号i+1
7. return 0; //退出循环，说明查找失败
8. }
单链表的定义
1. typedef struct LNode{ //定义单链表结点类型
2. ElemType data; //数据域
3. struct LNode *next; //指针域
4. }LNode, *LinkList;
采用头插法建立单链表
该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后，如图2-4所示。
图2-4 头插法建立单链表
头插法建立单链表的算法如下：
1. LinkList CreatList1(LinkList &L){
2. //从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
3. LNode *s;int x;
4. L=(LinkList)malloc(sizeof(LNode)); //创建头结点
5. L->next=NULL; //初始为空链表
6. scanf("%d", &x); //输入结点的值
7.
8. while(x!=9999) { //输入 9999 表示结束
9. s=(LNode*)malloc(sizeof(LNode) ); //创建新结点
10. s->data=x;
11. s->next=L->next; //重点（如果使用头插法的话）
12. L->next=s; //将新结点插入表中，L为头指针
13. scanf ("%d", &x);
14. } //while 结束
15.
16. return L;
17. }
采用尾插法建立单链表 头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r,使其始终指向当前链表的尾结点，如图2-5所示。
图2-5 尾插法建立单链表
尾插法建立单链表的算法如下：
1. LinkList CreatList2(LinkList &L){
2. //从表头到表尾正向建立单链表L,每次均在表尾插入元素
3. int x; // 设元素类型为整型
4.
L=(LinkList)malloc(sizeof(LNode));
5.
LNode *s, *r=L; //r 为表尾指针
6. scanf
("%d", &x); //输入结点的值
7.
8. while
(x!=9999) { //输入 9999 表示结束
9.
s=(LNode *)malloc(sizeof(LNode));
10. s->data=x; //重点
11.
r->next=s;
12.
r=s; //r指向新的表尾结点
13.
scanf ("%d", &x);
14. }
15.
16.
r->next = NULL;
//尾结点指针置空
17. return L;
18. }
按序号查找结点值
在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。
按序号查找结点值的算法如下：
1. LNode GetElem(LinkList L,int i){
2. //本算法取出单链表L（带头结点）中第i个位置的结点指针
3. int j=1; //计数，初始为1
4. LNode *p = L->next; //头结点指针赋给p //注意
5.
6. if(i==0)
7. return L; //若i等于0，则返回头结点
8. if(i<1)
9. return NULL; //若 i 无效，则返回 NULL
10.
11. while( p && j
12. p=p->next;
13. j++;
14. }
15.
16.
return p;
//返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即可
17. }
按值查找表结点
从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针。若整个单链表中没有这样的结点，则返回NULL。按值查找结点的算法如下：
1.
LNode
LocateElem
(LinkList L, ElemType e)
{
//本算法查找单链表 L （带头结点）中数据域值等于e的结点指针，否则返回NULL
2. LNode *p=L->next;
3. while( p!=NULL && p->data!=e) //从第1个结点开始查找data域为e的结点
4. p=p->next;
5.
6. return p; //找到后返回该结点指针，否则返回NULL
7. }
插入结点操作
插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。
算法首先调用上面的按序号查找算法GetElem(L, i-1)，查找第i-1个结点。假设返回的第i-1个结点为*p，然后令新结，点*s的指针域指向*p的后继结点，再令结点*p的指针域指向新插入的结点*s。其操作过程如图2-6所示。
图2-6 单链表的插入操作
实现插入结点的代码片段如下： 1.
p=GetElem(L, i-1) ; // 语句①，查找插入位置的前驱结点
2.
s->next=p->next; // 语句②，图 2-6 中辑作步骤 1
3. p->next=s; // 语句③，图2-6中操作步骤2
删除结点操作
删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i-1个结点，即被删结点的前驱结点，再将其删除。其操作过程如图2-7所示。
图2-7 单链表结点的删除
假设结点*p为找到的被删结点的前驱结点，为了实现这一操作后的逻辑关系的变化，仅需修改*p的指针域，即将*p的指针域next指向*q的下一结点。
实现删除结点的代码片段如下：
1. p=GetElem(L,i-1); //查找删除位置的前驱结点
2. q=p->next; //令q指向被删除结点
3. p->next=q->next //将*q结点从链中“断开”
4. free (q) ; //释放结点的存储空间
和插入算法一样，该算法的主要时间也是耗费在查找操作上，时间复杂度为O(n)。
扩展：删除结点*p
