数据结构C语言算法大全

1、....1)插入操作在顺序表L的第i (1<=L.length+1)个位置插入新元素 e。如果i的输入不合法，则返回false ,表示插入失败；否则，将顺序表的第i个元素以及其后的元素右移一个位置，腾出一个空位置插入新元素e,顺序表长度增加1，插入成功，返回true。bool ListInsert(SqList & L, int i, ElemType e)/本算法实现将元素e插入到顺序表L中第i个位置if ( i<1 | i>L.length+1 )return false; /判断i的范围是

2、否有效if(L.le ngth>= MaxSize)return false; /当前存储空间已满，不能插入for (int j =L.length; j >=i; j-)/将第i个位置及之后的元素后移L.dataj=L.dataj-l;L.datai-1= e; /在位置i处放入eL.length+; /线性表长度加 1return true;2)删除操作删除顺序表L中第i (1<=i<=L.length)个位置的元素，成功则返回true,否则返回false，并 将被删除的元素用引用变量 e返回。复制纯文本新窗口bool ListDelete(SqList &

3、 L,int i, int &e)本算法实现删除顺序表L中第i个位置的元素if(i<1 | i>Len gth)return false; /判断i的范围是否有效 e=L.datai-1 ; /将被删除的元素赋值给efor (int j=i; j<L.length;j+) 将第i个位置之后的元素前移L.dataj-1=L.dataj;8. L.le ngth-;/线性表长度减19. return true;10. 3）按值查找（顺序查找）在顺序表L中查找第一个元素值等于 e的元素，并返回其下标。1. int LocateElem（SqList L , ElemType

4、 e）2. 本算法实现查找顺序表中值为e的元素，如果查找成功，返回元素位序,返回0否则3. int i;4. for (i=0;i<L.le ngth;i+)5. if(L.datai=e)6. return i+1;/下标为i的元素值等于e,返回其位号i+17. return 0;退出循环，说明查找失败8. 单链表的定义1. typedef struct LNode /定义单链表结点类型2. ElemType data; /数据域3. struct LNode *n ext; 指针域4. LNode , *LinkList ;米用头插法建立单链表该方法从一个空表开始， 生成新结点，并将

5、读取到的数据存放到新结点的数据域中,新结点插入到当前链表的表头，即头结点之后，如图2-4所示。然后将..4.15.16.return L;图2-4头插法建立单链表头插法建立单链表的算法如下:LinkListCreatList1 (LinkList & L)从表尾到表头逆向建立单链表L,每次均在头结点之后插入元素LNode *s;int x;L=(LinkList )malloc(sizeof(LNode); 创建头结点L->next=NULL ;/初始为空链表scanf("%d", & x

6、);输入结点的值while (x!=9999) /输入 9999 表示结束s=(LNode *)malloc (sizeof(LNode);/创建新结点s->data=x;&>n ext=L-> next;重点(如果使用头插法的话)L->next=s; 将新结点插入表中，L为头指针scanf ("%d", & x); /while 结束采用尾插法建立单链表头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致， 可采用尾插法。该方法是将新结点插入到当前链表的表尾上， 为此必须增加一个尾指针r

7、,使其始终指向当前链表的尾结点，如图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

8、);10.s->data=x;/ 重点11.r->n ext=s;12.r= s; r指向新的表尾结点13.scanf ("%d", & x);14.15.16.r->next = NULL ; II尾结点指针置空17.return L;按序号查找结点值在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。按序号查找结点值的算法如下：1. LNode GetElem(LinkList L ,int i)2. 本算法取出单链表 L (带头结点)中第i个位置的结点指针3. in t j=1

9、; /计数，初始为14. LNode *p = L-> next; 头结点指针赋给 p /注意5.5. if(i=0)6. return L; 若i等于0,则返回头结点7. if(i<1)8. return NULL ;/若 i 无效，则返回 NULL10.9. while ( p && j<i )从第1个结点开始找，查找第i个结点10. p=p->n ext;11. j+;12. 15.13. return p; /返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即 可14. 按值查找表结点从单链表第一个结点开始，由前往后依次比较表中各结

10、点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针。若整个单链表中没有这样的结点，则返回NULL。按值查找结点的算法如下：1.LNode LocateElem (LinkList L , ElemType e) 本算法查找单链表L (带头结点)中数据域值等于e的结点指针，否则返回 NULL2. LNode *p=L->n ext;3. while ( p!=NULL && p->data!=e) /从第1个结点开始查找 data域为e的结点4. p=p->n ext;5.5. return p; 找到后返回该结点指针，否则返回NULL6. 插入结

11、点操作插入操作是将值为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中辑作步骤 13.

12、 p->next=s; /语句，图2-6中操作步骤2删除结点操作删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i-1个结点，即被删结点的前驱结点，再将其删除。其操作过程如图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

13、) ; /释放结点的存储空间和插入算法一样，该算法的主要时间也是耗费在查找操作上，时间复杂度为0(n)。扩展：删除结点*p要实现删除某一个给定结点 *p，通常的做法是先从链表的头结点开始顺序找到其前驱结点,然后再执行删除操作即可，算法的时间复杂度为0(n)。其实，删除结点*p的操作可以用删除*p的后继结点操作来实现，实质就是将其后继结点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为0(1)。实现上述操作的代码片段如下:1. q=p->next; 令q向*p的后继结点2. p->data=p-> next->data; /和后继结点交换数据域3. p->ne

14、xt=q->next; 将*q结点从链中 断开” 问题4. free (q) ; /释放后继结点的存储空间双链表双链表中结点类型的描述如下：1. typedef struct DNode /定义双链表结点类型2. ElemType data; / 数据域3. struct DNode * prior, * next; 前驱和后继指针4. DNode, *DLinklist ;双链表仅仅是在单链表的结点中增加了一个指向其前驱的prior指针，因此，在双链表中执行按值查找和按位查找的操作和单链表相同。但双链表在插入和删除操作的实现上，和单链表有着较大的不同。这是因为“链”变化时也需要对pri

15、or指针做出修改，其关键在于保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除结 点算法的时间复杂度仅为O(1)。双链表的插入操作在双链表中p所指的结点之后插入结点*s，其指针的变化过程如图2-9所示。插入操作的代码片段如下：1. s->next=p->next; /语句，将结点*s插入到结点*p之后2. p->next->prior=s; / 语句3. s->prior=p; / 语句4. p->next=s; / 语句图2-9双链表插入结点过程上述代码的语句顺序不是唯一的，但也不是任意的，两步必须在步之前，否则*p的后继结

16、点的指针就丢掉了，导致插入失败。为了加深理解，读者可以在纸上画出示意图。若 问题改成要求在结点*p之前插入结点*s，请读者思考具体的操作步骤。双链表的删除操作删除双链表中结点*p的后继结点*q，其指针的变化过程如图2-10所示。删除操作的代码片段如下：1. p->next=q->next; 图 2-10 中步骤2. q->next->prior=p; /图 2-10 中步骤3. free (q) ; /释放结点空间栈的基本操作各种辅导书中给出的基本操作的名称不尽相同，但所表达的意思大致是一样的。这里我们以严蔚敏编写的教材为准给出栈的基本操作，希望读者能熟记下面的基本操作

17、：Ini tStack(&S):初始化一个空栈 S。StackEmpty(S):判断一个栈是否为空，若栈S为空返回true，否则返回false。Push(&S, x):进栈，若栈S未满，将x加入使之成为新桟顶。Pop(&S, &x):出栈，若栈 S非空，弹出栈顶元素，并用x返回。GetTop(S, &x):读栈顶元素，若栈 S非空，用x返回栈顶元素。ClearStack(&S):销毁栈，并释放栈 S占用的存储空间。注意：符号&是C+特有的，用来表示引用，有的书上釆用C语言中的指针类型 *'，也可以达到传址的目的。在解答算法题时，若

18、题干没有做出限制，可以直接使用这些基本的操作函数。1.栈的顺序存储结构/ 栈的顺序存储表示 #defi ne STACK_INIT_SIZE 100;#defi ne STACKINCREMENT 10;typedef struct SElemType *base;SElemType *top;int stacksize; SqStack;Status In itStack (SqStack &S)/构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType);if (!S.base) exit (OVERFLOW)

19、; / 存储分配失败S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;Status Push (SqStack &S, SElemType e) if (S.top - S.base >= S.stacksize) /栈满，追加存储空间*sizeofS.base = (ElemType *) realloc ( S.base,(S.stacksize + STACKINCREMENT)(ElemType);if (!S.base) exit (OVERFLOW); /存储分配失败S.top = S.base + S.st

20、acksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK;Status Pop (SqStack &S, SElemType &e) /若栈不空，则删除 S的栈顶元素，用e返回其值，并返回 OK ；/否则返回ERRORif (S.top = S.base) return ERROR;e = *-S.top;return OK;链队列：typedef struct QNode / 结点类型QElemType data;struct QNode *next; QNode, *QueuePtr; 链队列链式映象 typed

21、ef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;Status InitQueue (LinkQueue & Q) / 构造一个空队列 QQ.front = Q.rear =(QueuePtr) malloc (sizeof (QNode); if (!Q.front) exit (OVERFLOW);/ 存储分配失败Q.front->next = NULL ; return OK;Status EnQueue (LinkQueue & Q,QElemType e) / 插入元

22、素 e 为 Q 的新的队尾元素p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); / 存储分配失败 p->data = e; p->next = NULL;Q.rear->next = p; Q.rear = p; return OK;Status DeQueue (LinkQueue & Q, QElemType & e) / 若队列不空，则删除 Q 的队头元素，/用e返回其值，并返回0K;否则返回ERROR if (Q.front = Q.rear) return ERROR;p

23、= Q.front->next; e = p->data; Q.front->next = p->next;if (Q.rear = p) Q.rear = Q.front; free (p); return OK;循环队列：#define MAXQSIZE 100 / 最大队列长度typedef struct QElemType *base; / 动态分配存储空间int front; / 头指针，若队列不空，/ 指向队列头元素int rear; / 尾指针，若队列不空，指向/ 队列尾元素 的下一个位置 SqQueue;循环队列顺序映象Status InitQueue

24、(SqQueue & Q) / 构造一个空队列 Q(ElemType);Q.base = (ElemType *) malloc (MAXQSIZE * sizeof if (!Q.base) exit (OVERFLOW);/ 存储分配失败Q.front = Q.rear = 0; return OK;Status EnQueue (SqQueue & Q, ElemType e) / 插入元素 e 为 Q 的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; / 队列满Q.baseQ.rear = e;Q.rea

25、r = (Q.rear+1) % MAXQSIZE;return OK;Status DeQueue (SqQueue & Q, ElemType & e) /若队列不空，则删除Q的队头元素，/用e返回其值，并返回OK;否则返回ERRORif (Q.front = Q.rear) return ERROR;e = Q.baseQ.fro nt;Q.fro nt = (Q.fro nt+1) % MAXQSIZE;return OK;经典算法：i.行编辑while (ch != EOF) /EOF为全文结束符while (ch != EOF && ch != &#

26、39;n') switch (ch) case # : Pop(S, c); break;case '': ClearStack(S); break;/ 重置 S 为空栈default : Push(S, ch); break;ch = getchar(); /从终端接收下一个字符 2.从原表达式求得后缀式的规律为：1) 设立操作数栈；2) 设表达式的结束符为"# ”，予设运算符栈的栈底为“# ”；3) 若当前字符是操作数，则直接发送给后缀式。4) 若当前运算符的优先数高于栈顶运算符，则进栈；5) 否则，退出栈顶运算符发送给后缀式；6) “(”对它之前后的运算

27、符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。算法：void tran sform(char suffix , char exp ) Ini tStack(S); Push(S,# );p = exp; ch = *p;while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch);else if ( ch!= #) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptreeswitch (ch) case(: Push(S, ch); break;cas

28、e): Pop(S, c);while (c!=() Pass( Suffix, c); Pop(S, c) break;defult :while(Gettop(S, c) && ( precede(c,ch) Pass( Suffix, c); Pop(S, c); if ( ch!= #) Push( S, ch);break; / switch3汉诺塔void hano i (i nt n, char x, char y, char z) /将塔座x上按直径由小到大且至上而下编号为 1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if (n=1)2 move

29、(x, 1, z); /将编号为1的圆盘从 x移到z3 else 4 hanoi(n-1, x,乙y); / 将x上编号为1至 n-1的/圆盘移到y, z作辅助塔5 move(x, n, z); /将编号为n的圆盘从 x移到z6 hanoi(n-1, y, x, z); / 将 y 上编号为1至 n-1 的/圆盘移到乙x作辅助塔7 8 树：二叉树的顺序存储：#defi ne MAX_TREE_SIZE 100/ 二叉树的最大结点数typedef TEIemType SqBiTreeMAX_TREE_SIZE;/ 0号单元存储根结点SqBiTree bt;二叉树的二叉链表存储：typedef s

30、truct BiTNode / 结点结构TEIemType data;struct BiTNode *l child, *r child;/ 左右孩子指针 BiTNode, * BiTree; 二叉树的三叉链表存储： typedef struct TriTNode / 结点结构TElemType data;struct TriTNode *l child, *r child;/ 左右孩子指针struct TriTNode *parent ; / 双亲指针 TriTNode, * TriTree; 二叉树的双亲链表存储： typedef struct BPTNode / 结点结构TElemTyp

31、e data;int * parent; / 指向双亲的指针char LRTag; / 左、右孩子标志域 BPTNode树的结构：typedef struct BPTree / 树结构BPTNode nodesMAX_TREE_SIZE;int num_node; / 结点数目int root; / 根结点的位置 BPTree树的先序遍历：void Preorder ( BiTree T, void ( *visit)(TElemType & e) / 先序遍历二叉树 if (T) visit(T->data) ; / 访问结点 Preorder( T-> l child,

32、 visit ); / 遍历左子树 Preorder( T-> rchild, visit );/ 遍历右子树 树的中序遍历递归算法： void In order ( BiTree T,void ( *visit)(TElemType & e) / 中序遍历二叉树if (T) Inorder( T-> lchild, visit ); / 遍历左子树 visit(T->data) ; / 访问结点Inorder( T-> r child, visit );/ 遍历右子树树的中序遍历非递归算法：BiTNode * GoFarLeft (BiTree T, Stac

33、k *S) if (!T ) return NULL ;while (T-> lchild ) Push(S, T);T = T-> lchild;return T;void Inorder_I(BiTree T, void (*visit) (TelemType & e)Stack *S;t = GoFarLeft (T, S); / 找到最左下的结点 while (t)visit(t->data);if (t-> rchild)t = GoFarLeft(t-> rchild, S);else if ( !StackEmpty(S ) / 栈不空时退栈 t = Pop(S);else t