数据结构C语言算法大全

1) 插入操作

在顺序表L的第i (1<=L.length+1)个位置插入新元素e。如果i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

bool ListInsert(SqList &L, int i, ElemType e){

//本算法实现将元素e插入到顺序表L中第i个位置 if ( i<1 || i>L.length+1 )

return false; // 判断i的范围是否有效 if(L.length>=MaxSize)

return false; // 当前存储空间已满，不能插入

for (int j =L.length; j >=i; j--) // 将第i个位置及之后的元素后移 L.data[j]=L.data[j-l]; L.data[i-1]=e; //在位置i处放入e L.length++; //线性表长度加1 return true; }

2) 删除操作

删除顺序表L中第i (1<=i<=L.length)个位置的元素，成功则返回true,否则返回false，并将被删除的元素用引用变量e返回。

复制纯文本新窗口 1. 2. 3. 4. 5. 6. 7.

bool ListDelete(SqList &L,int i, int &e){

//本算法实现删除顺序表L中第i个位置的元素 if(i<1 || i>L.length)

return false; // 判断i的范围是否有效 e=L.data[i-1] ; // 将被删除的元素赋值给e

for (int j=i; j

8. 9. 10.

L.length--; //线性表长度减1 return true; }

3) 按值查找（顺序查找）

在顺序表L中查找第一个元素值等于e的元素，并返回其下标。

1. 2.

返回0

int LocateElem(SqList L, ElemType e){

//本算法实现查找顺序表中值为e的元素，如果查找成功，返回元素位序，否则

3. 4. 5. 6. 7. 8.

int i;

for(i=0;i

return i+1; // 下标为i的元素值等于e，返回其位号i+1 return 0; //退出循环，说明查找失败 }

单链表的定义 1. 2. 3. 4.

typedef struct LNode{ //定义单链表结点类型 ElemType data; //数据域 struct LNode *next; //指针域 }LNode, *LinkList;

采用头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后，如图2-4所示。

图2-4 头插法建立单链表

头插法建立单链表的算法如下：

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

LinkList CreatList1(LinkList &L){

//从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素 LNode *s;int x;

L=(LinkList)malloc(sizeof(LNode)); //创建头结点 L->next=NULL; //初始为空链表 scanf(\, &x); //输入结点的值

while(x!=9999) { //输入 9999 表示结束

s=(LNode*)malloc(sizeof(LNode) ); //创建新结点 s->data=x;

s->next=L->next; //重点（如果使用头插法的话） L->next=s; //将新结点插入表中，L为头指针 scanf (\, &x); } //while 结束

return L; }

采用尾插法建立单链表

头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r,使其始终指向当前链表的尾结点，如图2-5所示。

图2-5 尾插法建立单链表

尾插法建立单链表的算法如下：

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.

LinkList CreatList2(LinkList &L){

//从表头到表尾正向建立单链表L,每次均在表尾插入元素 int x; // 设元素类型为整型 L=(LinkList)malloc(sizeof(LNode)); LNode *s, *r=L; //r 为表尾指针 scanf (\, &x); //输入结点的值

while (x!=9999) { //输入 9999 表示结束 s=(LNode *)malloc(sizeof(LNode)); s->data=x; //重点 r->next=s;

r=s; //r指向新的表尾结点 scanf (\, &x); }

r->next = NULL; //尾结点指针置空 return L; }

按序号查找结点值

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。 按序号查找结点值的算法如下：

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

可

LNode GetElem(LinkList L,int i){

//本算法取出单链表L（带头结点）中第i个位置的结点指针 int j=1; //计数，初始为1

LNode *p = L->next; //头结点指针赋给p //注意

if(i==0)

return L; //若i等于0，则返回头结点 if(i<1)

return NULL; //若 i 无效，则返回 NULL

while( p && jnext; j++; }

return p; //返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即

17.

}

按值查找表结点

从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针。若整个单链表中没有这样的结点，则返回NULL。按值查找结点的算法如下：