300字范文 > 严蔚敏版数据结构（C语言版）算法实现代码

严蔚敏版数据结构（C语言版）算法实现代码

时间：2019-02-25 08:49:30

数据结构（C语言版）代码实现线性表顺序表链表单向链表静态链表01静态链表02双向循环链表栈与队列栈顺序栈进制转换行编辑器未完待续。。。

数据结构（C语言版）代码实现

部分采用C++的语法实现

线性表

顺序表与链表

顺序表

代码如下：

#include <bits/stdc++.h>using namespace std;#define MaxSize 100#define ElemType int#define Status int#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ERROR 0#define OK 1#define INFEASIBLE -1#define TRUE 1#define FALSE 0/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */typedef struct {ElemType * elem; int length; int listSize; }SqList;Status CmpGreater(ElemType data, ElemType e) {return data > e ? TRUE : FALSE;}Status CmpSame(ElemType data, ElemType e) {return data == e ? TRUE : FALSE;}void visit(ElemType *c) /* ListTraverse()调用的函数(类型要一致) */{printf("%d ",*c);}Status ClearList(SqList &L){/* 将L重置为空表 */L.length = 0;return OK;}Status DestoryList(SqList &L){/* 销毁顺序线性表L */delete(L.elem);L.elem = NULL;L.length = 0;L.listSize = 0;return OK;}bool ListEmpty(SqList L){if (0 == L.length)return true;return false;}Status GetElem(SqList L, int i, ElemType &e){if (i < 1 || i > L.length)exit(ERROR);e = *(L.elem + i - 1);return OK;}Status PriorElem(SqList L, ElemType e, ElemType &pre_e){/* 若e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， *//* 否则操作失败，pre_e无定义 */int i = 2;ElemType * p = L.elem + 1;while (i <= L.length && *p != e){p++;i++;}if (i > L.length) return INFEASIBLE;pre_e = *(--p);return OK;}Status NextElem(SqList L, ElemType e, ElemType next_e){/* 若e是L的数据元素，且不是最后一个，则用next_e返回它的后继， *//* 否则操作失败，next_e无定义 */int i = 1;ElemType *p = L.elem;while (i < L.length && *p != e){i++;p++;}if (i == L.length) return INFEASIBLE;next_e = *(++p);return OK;}Status InitList_Sq(SqList &L){/* 初始化线性表 */L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));if (! L.elem) exit(OVERFLOW);L.length = 0;L.listSize = LIST_INIT_SIZE;return OK;}Status ListInsert_Sq(SqList &L, int i, ElemType e){/* 在L中第i个位置之前插入新的数据元素e，L的长度加1 */if (i < 1 || i > L.length + 1) return ERROR;if (L.length >= L.listSize){ElemType *newbase = (ElemType *)realloc(L.elem, (L.listSize + LISTINCREMENT) * sizeof(ElemType));if (NULL == newbase) exit(OVERFLOW);L.elem = newbase;L.listSize += LISTINCREMENT;}for (int j = L.length - 1; j >= i - 1; j++)L.elem[j + 1] = L.elem[j];L.elem[i - 1] = e;L.length ++;return OK;}Status ListDelete_Sq(SqList &L, int i, ElemType &e){if (i < 1 || i > L.length) return ERROR;e = L.elem[i - 1];for (int j = i - 1; j < L.length - 1; j++)L.elem[j] = L.elem[j + 1];L.length --;return OK;}Status LocateElem(SqList L, ElemType e, Status(* compare)(ElemType, ElemType)){/* 在顺序表L中查找第一个值与e满足compare()的元素位序 */int i = 1;ElemType *p = L.elem;/* int j = 0;while (i <= L.length && !(* compare)(L.elem[j++], e)); */while (i <= L.length && !(* compare)(* p++, e)) ++i;if (i <= L.length) return i;else return 0;}void Merge_Sq(SqList La, SqList Lb, SqList &Lc){/* 已知顺序线性表La和Lb的元素按值非递减排列 *//* 归并La和Lb得到新的顺序线性表Lc, Lc的元素也按值非递减排序 */ElemType *pa = La.elem, *pb = Lb.elem;Lc.listSize = Lc.length = La.length + Lb.length;ElemType *pc = Lc.elem = (ElemType *)malloc(Lc.listSize * sizeof(ElemType));if (NULL == Lc.elem) exit(OVERFLOW);ElemType *pa_last, *pb_last;pa_last = La.elem + La.length - 1;pb_last = Lb.elem + Lb.length - 1;while (pa <= pa_last && pb <= pb_last){if (*pa < *pb) *pc++ = *pa++;else *pc++ = *pb++;}while (pa <= pa_last) *pc++ = *pa++;while (pb <= pb_last) *pc++ = *pb++;}void union_Sq(SqList &La, SqList Lb){/* 将线性表在Lb中但不在La中的数据元素插入到La中 */for (int i = 1; i <= Lb.length; i++){if (LocateElem(La, Lb.elem[i - 1], CmpSame))ListInsert_Sq(La, La.length++, Lb.elem[i - 1]);}}Status ListTraverse(SqList L, void(*vi)(ElemType*)){/* 依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败 */ElemType * p = L.elem;for (int i = 1; i <= L.length; i++)vi(p++);cout << endl;return OK;}void InsertAscend(SqList &L, ElemType e){/* 在L中按非降序插入新的数据元素e，L的长度加1 */ElemType *newbase, *p;int k;if (L.length >= (L.listSize)){newbase = (ElemType *)realloc(L.elem, (L.listSize + LISTINCREMENT) * sizeof(ElemType));if (!newbase)exit(OVERFLOW);L.elem = newbase;L.listSize += LISTINCREMENT;}p = L.elem;for (k = 1; k <= L.length; k++)if(e > *p)p++;elsebreak;ListInsert_Sq(L, k, e);}int main(int argc, char const *argv[]){SqList L; ElemType e;cout << "InitList_Sq" << endl;InitList_Sq(L);cout << "ListEmpty" << endl;if(ListEmpty(L) == TRUE) cout << "L is empty" << endl;elsecout << "L is not empty" << endl;cout << "ListInsert" << endl;for (int i = 1; i <= 12; i++)ListInsert_Sq(L, i, 2 * i);cout << "ListTraverse" << endl;ListTraverse(L, visit);cout << "ListDelete" << endl;ListTraverse(L, visit); if(OK == ListDelete_Sq(L, 5, e))cout << "Delete " << e << "successfully" << endl;elsecout << "NOT FOUND" << endl;ListTraverse(L, visit);cout << "GetElem" << endl;GetElem(L, 3, e);cout << "LocateElem" << endl;int i = LocateElem(L, 7, CmpGreater);cout << L.elem[i - 1] << endl;cout << "PriorElem" << endl;ElemType cur_e = 4; if(OK == PriorElem(L, cur_e, e))cout << e << endl;elsecout << "NOT FOUND" << endl;cout << "NextElem" << endl;cur_e = 5; if(OK == NextElem(L, cur_e, e))cout << e << endl;elsecout << "NOT FOUND" << endl;cout << "ClearList" << endl;cout << "Before cleaning" << endl;if(TRUE == ListEmpty(L))cout << "L is empty" << endl;else cout << "L is not empty" << endl;ClearList(L);cout << "After cleaning" << endl;if(TRUE == ListEmpty(L))cout << "L is empty" << endl;else cout << "L is not empty" << endl;cout << "Before destruction" << endl;if(L.elem != NULL) cout << "Exist" << endl;elsecout << "Does not exist" << endl;DestoryList(L);cout << "After destruction" << endl;if(L.elem != NULL) cout << "Exist" << endl;elsecout << "Does not exist" << endl;return 0;}

运行结果如下：

链表

单向链表

#include <bits/stdc++.h>using namespace std;#define MaxSize 100#define ElemType int#define Status int#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ERROR 0#define OK 1#define INFEASIBLE -1#define TRUE 1#define FALSE 0typedef struct LNode{ElemType data; // data为抽象元素类型struct LNode *next; // next为指针类型}LNode, *LinkList;void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */{printf("%d ",c);}Status CmpGreater(ElemType data, ElemType e) {return data > e ? TRUE : FALSE;}Status DestoryList(LinkList &L){// 销毁链表LinkList p;if (NULL == L) // 确保链表存在return ERROR;p = L;while (p != NULL){p = L->next;free(L);L = p;}L = NULL;return OK;}Status CleaeList(LinkList &L){// 链表置空LinkList p, q;if (NULL == L)return ERROR;p = L->next;while (p != NULL){q = p;p = p->next;free(q);}L->next = NULL;return OK;}Status ListEmpty(LinkList L){// 判断链表是否为空bool flag = (NULL == L->next && NULL != L) ? true : false;if (flag) return TRUE;return FALSE;}int ListLength(LinkList L){// 返回链表元素个数if (NULL == L || NULL == L->next)return 0;int count = 0;LinkList p = L->next;while (p){count ++;p = p->next;}return count;}int LocateElem(LinkList L, ElemType e, Status(Compare)(ElemType, ElemType)){// 返回首个与e满足Compare关系的元素位序if (NULL == L || NULL == L->next)return 0;int i = 1;LinkList p = L->next;if (p != NULL && !Compare(p->data, e)){i++;p = p->next;}if (p != NULL) return i;return 0;}Status PriorElem(LinkList L, ElemType cur, ElemType &pre){// 返回前驱if (NULL == L || NULL == L->next)return ERROR;LinkList p = L->next;if (p->data == cur) // 无前驱return ERROR;LinkList q = p->next;if (q != NULL && q->data != cur){p = q;q = q->next;}if (NULL == q)return ERROR;pre = p->data;return OK;}Status NextElem(LinkList L, ElemType cur, ElemType &nex){// 返回后继if (NULL == L || NULL == L->next)return ERROR;LinkList p = L->next;if (p->next != NULL && p->data != cur)p = p->next;if (NULL == p->next)return ERROR;nex = p->next->data;return OK;}void ListTraverse(LinkList L, void(visit)(ElemType)){// 遍历if (NULL == L || NULL == L->next)return;LinkList p = L->next;while (p != NULL){visit(p->data);p = p->next;}putchar('\n');}LinkList creatNode01(){// 生成先进先出单链表（链式队列）LinkList head, tail, p;head = (LinkList)malloc(sizeof(LNode));ElemType e;tail = head;scanf("%d", &e);while (e != 0){p = (LinkList)malloc(sizeof(LNode));p->data = e;tail->next = p;tail = p;scanf("%d", &e);}tail->next = NULL;return head;}LinkList creatNode02(){// 生成后进先出单链表（链式栈）LinkList head, p;ElemType e;head = (LinkList)malloc(sizeof(LNode));head->next = NULL;scanf("%d", &e);while(e != 0){p = (LinkList)malloc(sizeof(LNode));p->data = e;p->next = head->next;head->next = p;scanf("%d", &e);}return head;}void creatNode03(LinkList &head, ElemType e){// 生成不带表头递增有序单链表算法LinkList q = NULL, p = head, f; // p,q扫描，查找插入位置while (p != NULL && e > p->data){q = p;p = p->next;}f = (LinkList)malloc(sizeof(LNode));f->data = e;if (NULL == p){f->next = NULL;if (NULL == q)head = f; // 对空表的插入elseq->next = f; // 作为最后一个结点插入}else if (NULL == q) // 作为第一个结点插入{f->next = p;head = f;}else // 一般情况插入新结点{f->next = p;q->next = f;}}void creatNode04(LinkList head, ElemType e){// 生成带表头递增有序单链表算法LinkList q = head, p = head->next, f;while (p && e > p->data){q = p;p = p->next;}f = (LinkList)malloc(sizeof(LNode));f->data = e;f->next = p;q->next = f;}Status IninList(LinkList &L){// 构建一个空的线性单链表L = (LinkList)malloc(sizeof(LNode));if (NULL == L) exit(OVERFLOW);L->next = NULL;return OK;}Status GetElem(LinkList L, int i, ElemType &e){// L为带头结点的单链表的头指针// 当第i个元素存在时，其值赋给e并返回OK,否则返回errorLinkList p = L->next;int j = 1;while (p && j < i){p = p->next;++j;}if (!p || j > i) return ERROR;e = p->data;return OK;}Status ListDelete(LinkList &L, int i, ElemType &e){// 在带头结点的单链表L中，删除第i个元素，并由e返回其值LinkList p = L;int j = 0;while (p->next && j next;++j;}if (!(p->next) || j > i - 1) return ERROR; // 删除位置不合理LinkList q = p->next;p->next = q->next;e = q->data;free(q);return OK;}Status NodeDelete(LinkList head, ElemType e){// 在带表头结点的单链表中删除值为e的结点LinkList q = head, p = head->next;while (p && p->data != e){q = p;p = p->next;}if (p){q->next = p->next;free(p);return OK;}elsereturn ERROR;}Status ListInsert(LinkList &L, int i, ElemType e){// 在带头结点的单链表L中第i个位置之前插入元素eLinkList p = L;int j = 0;while (p && j next;++j;}if (!p || j > i - 1) return ERROR;LinkList s = (LinkList)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return OK;}void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc){// 归并La,Lb得到LcLinkList pa = La->next, pb = Lb->next, pc;La = pc = La; // 用La的头结点作为Lc的头结点while (pa && pb){if (pa->data <= pb->data){pc->next = pa;pc = pa;pa = pa->next;}else{pc->next = pb;pc = pb;pb = pb->next;}}pc->next = pa ? pa : pb; // 插入剩余段free(Lb);La = NULL;Lb = NULL;}int main(int argc, char const *argv[]){cout << "creatNode01" << endl;LinkList L1 = creatNode01();ListTraverse(L1, visit);cout << "creatNode02" << endl;LinkList L2 = creatNode02();ListTraverse(L2, visit);cout << "creatNode03" << endl;LinkList head1 = NULL;ElemType e;cin >> e;while (e != 0){creatNode03(head1, e);cin >> e;}cout << "creatNode04" << endl;LinkList head2 = (LinkList)malloc(sizeof(LNode));head2->next = NULL;cin >> e;while (e != 0){creatNode04(head2, e);cin >> e;}cout << "IninList" << endl;LinkList L;IninList(L);cout << "ListEmpty" << endl;ListEmpty(L) ? cout << "Yes" : cout << "No";cout << endl;cout << "ListInsert" << endl;for (int i = 1; i <= 8; i++)ListInsert(L, i, 2 * i);cout << "ListTraverse" << endl;ListTraverse(L, visit);cout << "ListLength" << endl;cout << ListLength(L) << endl;cout << "ListDelete" << endl;OK == ListDelete(L, 6, e) ? cout << e : cout << "ERROR";cout << endl;ListTraverse(L, visit);cout << "GetElem" << endl;cout << GetElem(L, 4, e);cout << "LocateElem" << endl;int i = LocateElem(L, 7, CmpGreater);GetElem(L, i, e);cout << e << endl;cout << "PriorElem" << endl;ElemType cur = 6;if (OK == PriorElem(L, cur, e))cout << e << endl;elsecout << "ERROR" << endl;cout << "NextElem" << endl;if (OK == NextElem(L, cur, e))cout << e << endl;elsecout << "ERROR" << endl;cout << "CleaeList" << endl;cout << "Before" << endl;ListEmpty(L) ? cout << "Yes" << endl : cout << "No" << endl;cout << "After" << endl;CleaeList(L);ListEmpty(L) ? cout << "Yes" << endl : cout << "No" << endl;cout << "DestoryList" << endl;cout << "Before" << endl;L ? cout << "Yes" << endl : cout << "No" << endl;DestoryList(L);cout << "After" << endl;L ? cout << "Yes" << endl : cout << "No" << endl;cout << "MergeList" << endl;LinkList Lc;MergeList(L1, L2, Lc);ListTraverse(Lc, visit);return 0;}

静态链表01

代码如下：

#include <bits/stdc++.h>using namespace std;#define MaxSize 1000#define ElemType int#define Status int#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ERROR 0#define OK 1#define INFEASIBLE -1#define TRUE 1#define FALSE 0/** space：指示备用空间* S：指示静态链表头结点索引*/// 线性表的静态单链表存储结构typedef struct {ElemType data;int cur;}component, SLinkList[MaxSize];Status CmpGreater(ElemType data, ElemType e) {return data > e ? TRUE : FALSE;}void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */{printf("%d ",c);}void InitSpace(SLinkList &space){// 将一位数组space中各分量链成一个备用链表，space[0].cur为透头指针// '0'表示空指针for (int i = 0; i < MaxSize - 1; ++i)space[i].cur = i + 1;space[MaxSize - 1].cur = 0;}int Malloc(SLinkList &space){// 若备用空间链表非空，则返回分配的结点下标，否则返回0// 为静态链表从备用空间申请结点空间,如果申请成功，返回可用空间的索引，申请失败时，返回0int i = space[0].cur;if (space[0].cur) // 将申请到的空间从备用空间中删去space[0].cur = space[i].cur;return i;}void Free(SLinkList &space, int k){// 将下标为k的空闲结点回收到备用链表space[k].cur = space[0].cur;space[0].cur = k;}Status InitList(SLinkList &space, int &s){// 初始化int index;InitSpace(space);index = Malloc(space);if (0 == index)return ERROR;space[index].cur = 0;s = index;return OK;}Status DestoryList(SLinkList &space, int &s){// 销毁int cur;if (0 == s)return ERROR;while (s != 0){cur = space[s].cur;Free(space, s);s = cur;}return OK;}Status ClearList(SLinkList &space, int s){// 置空int p, cur;if (0 == s)return ERROR;// 获取静态链表首个结点的索引p = space[s].cur;while (p != 0){cur = space[p].cur;Free(space, p);p = cur;}space[s].cur = 0;return OK;}Status ListEmpty(SLinkList space, int s){// 判读是否为空if (s != 0 && 0 == space[s].cur)return TRUE;return FALSE;}int ListLength(SLinkList space, int s){// 有效元素个数if (0 == s || 0 == space[s].cur)return ERROR;s = space[s].cur;int count = 0;while (s != 0){count ++;s = space[s].cur;}return count;}Status GetElem(SLinkList space, int s, int i, ElemType &e){// 获取元素值if (0 == s || 0 == space[s].cur)return ERROR;s = space[s].cur;int count = 0;while (s != 0 && count < i - 1){count++;s = space[s].cur;}e = space[s].data;return OK;}int LocateElem(SLinkList space, int s, ElemType e, Status(Compare)(ElemType, ElemType)){// 查找if (0 == s || 0 == space[s].cur)return 0;int i = 1, p = space[s].cur;while (p != 0 && !Compare(space[p].data, e)){i++;p = space[p].cur;}if (p != 0)return i;return 0;}Status PriorElem(SLinkList space, int s, ElemType cur, ElemType &pre){// 前驱元素if (0 == s || 0 == space[s].cur)return ERROR;int p, q;p = space[s].cur;// 第一个元素无前驱if (space[p].data == cur)return ERROR;q = space[p].cur; // 指向第二个元素while (q != 0 && space[q].data != cur){p = q;q = space[q].cur;}if (0 == q)return ERROR;pre = space[p].data;return OK;}Status NextElem(SLinkList space, int s, ElemType cur, ElemType &nex){// 后继元素if (0 == s || 0 == space[s].cur)return ERROR;int pre = space[s].cur;while (space[pre].cur != 0 && space[pre].data != cur)pre = space[pre].cur;if (0 == space[pre].cur)return ERROR;nex = space[space[pre].cur].data;return OK;}Status ListInsert(SLinkList &space, int s, int i, ElemType e){// 插入元素if (0 == s)return ERROR;int p = s, q, j = 0;while (p != 0 && j i - 1)return ERROR;q = Malloc(space);space[q].data = e;space[q].cur = space[p].cur;space[p].cur = q;return OK;}Status ListDelete(SLinkList &space, int s, int i, ElemType &e){// 删除if (0 == s)return ERROR;int p = s, j = 0;while (space[p].cur != 0 && j i - 1)return ERROR;int q = space[p].cur;space[p].cur = space[q].cur;e = space[q].data;Free(space, q);return OK;}void ListTraverse(SLinkList space, int s, void(visit)(ElemType)){// 遍历if (0 == s || 0 == space[s].cur)return;int p = space[s].cur;while (p != 0){visit(space[p].data);p = space[p].cur;putchar('\n');}}void PrintList(SLinkList space, int s) {int i = 0;printf("==== 备用空间 ====\n");while(i < 20) {printf("%2d | %2d | %2d |\n", i, space[i].data, space[i].cur);i = space[i].cur;}printf("==== 静态链表 ====\n");i = s;while(i > 0 && i < 20) {printf("%2d | %2d | %2d |\n", i, space[i].data, space[i].cur);i = space[i].cur;}}int main(int argc, char const *argv[]){SLinkList space;int s;cout << "InitSpace" << endl;InitList(space, s);cout << "ListEmpty" << endl;ListEmpty(space, s) ? cout << "yes\n" : cout << "no\n";cout << "ListInsert" << endl;for (int i = 0; i <= 8; i++)ListInsert(space, s, i, 2 * i);cout << "ListTraverse" << endl;ListTraverse(space, s, visit);cout << "ListLength" << endl;cout << ListLength(space, s);cout << "ListDelete" << endl;cout << "Before" << endl;ListTraverse(space, s, visit);cout << "After" << endl;ElemType e;if(OK == ListDelete(space, s, 5, e))cout << "Delete " << e << "successfully" << endl;elsecout << "NOT FOUND" << endl;ListTraverse(space, s, visit);cout << "GetElem" << endl;GetElem(space, s, 3, e);cout << "LocateElem" << endl;int i = LocateElem(space, s, 7, CmpGreater);cout << space[i - 1].data << endl;cout << "PriorElem" << endl;ElemType cur_e = 4; if(OK == PriorElem(space, s, cur_e, e))cout << e << endl;elsecout << "NOT FOUND" << endl;cout << "NextElem" << endl;cur_e = 5; if(OK == NextElem(space, s, cur_e, e))cout << e << endl;elsecout << "NOT FOUND" << endl;cout << "ClearList" << endl;cout << "Before cleaning" << endl;if(TRUE == ListEmpty(space, s))cout << "L is empty" << endl;else cout << "L is not empty" << endl;ClearList(space, s);cout << "After cleaning" << endl;if(TRUE == ListEmpty(space, s))cout << "L is empty" << endl;else cout << "L is not empty" << endl;cout << "Before destruction" << endl;if(s != 0) cout << "Exist" << endl;elsecout << "Does not exist" << endl;DestoryList(space, s);cout << "After destruction" << endl;if(s != 0) cout << "Exist" << endl;elsecout << "Does not exist" << endl;return 0;}

静态链表02

#include <bits/stdc++.h>using namespace std;#define MaxSize 1000#define ElemType int#define Status int#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ERROR 0#define OK 1#define INFEASIBLE -1#define TRUE 1#define FALSE 0typedef struct {ElemType data;int cur;}component, SLinkList[MaxSize];void InitSpace(SLinkList &space){// 将一位数组space中各分量链成一个备用链表，space[0].cur为头指针// '0'表示空指针for (int i = 0; i < MaxSize - 1; ++i)space[i].cur = i + 1;space[MaxSize - 1].cur = 0;}int Malloc(SLinkList &space){// 若备用空间链表非空，则返回分配的结点下标，否则返回0// 为静态链表从备用空间申请结点空间,如果申请成功，返回可用空间的索引，申请失败时，返回0int i = space[0].cur;if (space[0].cur) // 将申请到的空间从备用空间中删去space[0].cur = space[i].cur;return i;}void Free(SLinkList &space, int k){// 将下标为k的空闲结点回收到备用链表space[k].cur = space[0].cur;space[0].cur = k;}void differencce(SLinkList &space, int &s){// 依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)U(B-A)的静态链表InitSpace(space);s = Malloc(space);int r = s, m, n;scanf("%d%d", &m, &n); // 输入A, B元素个数for (int j = 1; j <= m; j++) //建立A的链表{int i = Malloc(space); //分配节点scanf("%d", &space[i].data); // 输入A的元素值space[r].cur = i;r = i; // 插入到表尾}space[r].cur = 0; // 尾结点的指针为空for (int j = 1; j <= n; j++) // 输入B的元素，若不在当前表中，则插入，否则删除{ElemType b;int p = s, k = space[s].cur; // k指向集合A的第一个节点scanf("%d", &b);while (k != space[r].cur && space[k].data != b){p = k;k = space[k].cur;}if (k == space[r].cur) // 当前表中不存在该元素，插入在r所指结点之后，而且r的位置不变{int i = Malloc(space);space[i].data = b;space[i].cur = space[r].cur;space[r].cur = i;}else // 元素已经在链表中，删除元素{space[p].cur = space[k].cur;Free(space, k);if (r == k) r = p;}}}int main(int argc, char const *argv[]){SLinkList space;int s;differencce(space, s);return 0;}

双向循环链表

typedef struct DuLNode{ElemType data;DuLNode * prior;DuLNode * next;}DuLNode, *LinkList;Status CmpGreater(ElemType data, ElemType e) {return data > e ? TRUE : FALSE;}Status CmpSame(ElemType data, ElemType e) {return data == e ? TRUE : FALSE;}void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */{printf("%d ",c);}Status InitList(LinkList &L){// 初始化双向循环链表L = (LinkList)malloc(sizeof(DuLNode));if (NULL == L) exit(OVERFLOW);L->next = L->prior = L; // 前驱和后继均指向自身return OK;}Status ClearList(LinkList &L){// 置空链表LinkList p,q;if (NULL == L)return ERROR;p = L->next;while (p != L){q = p->next;free(p);p = q;}L->next = L->prior = L;return OK;}Status DestoryList(LinkList &L){// 销毁链表if (NULL == L)return ERROR;ClearList(L);free(L);L = NULL;return OK;}Status ListEmpty(LinkList L){// 判断链表是否为空if (L != NULL && L->next == L && L->prior == L)return TRUE;return FALSE;}int ListLength(LinkList L){// 链表有效元素长度if (NULL == L || L->next == L || L->prior == L)return 0;int count = 0;LinkList p = L->next;while (p != L){count++;p = p->next;}return count;}Status GetElem(LinkList L, int i, ElemType &e){// 获取链表第i个元素的值if (NULL == L || L->next == L || L->prior == L)return ERROR;LinkList p = L;int j = 0;while (p->next != L && j <= i - 1){p = p->next;j++;}if (p->next == L || j > i - 1)return ERROR;e = p->next->data;return OK;}int LocateElem(LinkList L, ElemType e, Status(Compare)(ElemType, ElemType)){// 查找与e满足compare()关系的第一个元素位置if (NULL == L || L->next == L || L->prior == L)return 0;int i = 1; LinkList p = L->next;while (p != L && !Compare(p->data, e)){i++;p = p->next;}if (p != L)return i;return 0;}Status PriorElem(LinkList L, ElemType cur, ElemType &pre){// 前驱if (NULL == L || L->next == L || L->prior == L)return ERROR;LinkList p = L->next;if (p->data == cur)return ERROR;p = p->next;while (p != L && p->data != cur)p = p->next;if (p == L)return ERROR;pre = p->prior->data;return OK;}Status NextElem(LinkList L, ElemType cur, ElemType &next){// 后继if (NULL == L || L->next == L || L->prior == L)return ERROR;LinkList p = L->next;while (p ->next != L && p->data != cur)p = p->next;if (p->next == L)return ERROR;next = p->next->data;return OK;}Status ListInsert(LinkList &L, int i, ElemType e){// 插入if (NULL == L)return ERROR;LinkList p = L;int j = 0;while (p != L && j <= i - 1){p = p->next;j++;}if (p->next == L || j > i - 1)return ERROR;LinkList s = (LinkList)malloc(sizeof(DuLNode));if (NULL == s)exit(OVERFLOW);s->data = e;s->prior = p->prior;p->prior->next = s;s->next = p;return OK;}Status ListDelete(LinkList L, int i, ElemType &e){// 删除节点if (NULL == L || L->next == L || L->prior == L)return ERROR;LinkList p = L;int j = 0;while (p != L || j next;j++;}if (p->next == L || j > i - 1 || p == L)return ERROR;e = p->data;p->prior->next = p->next;p->next->prior = p->prior;free(p);return OK;}void ListTraverse(LinkList L, void(visit)(ElemType)){// 遍历链表if (NULL == L || L->next == L || L->prior == L)return;LinkList p = L->next;while (p != L){visit(p->data);p = p->next;}putchar('\n');}

栈与队列

栈

顺序栈

#include <bits/stdc++.h>#define MaxSize 100#define SElemType int#define Status int#define ERROR 0#define OK 1#define INFEASIBLE -1#define TRUE 1#define FALSE 0using namespace std;#define STACK_INIT_SIZE 100// 存储空间的初始分配量#define STACKINCREMENT 10// 存储空间的分配增量typedef struct {SElemType *base; // 在构造和销毁之前，base的值为NULLSElemType *top; // 栈顶指针int stacksize; // 已分配的内存空间}SqStack;Status InitStack(SqStack &s){// 初始化s.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (NULL == s.base)exit(OVERFLOW);s.top = s.base;s.stacksize = STACK_INIT_SIZE;return OK;}Status DestoryStack(SqStack &s){// 销毁顺序栈free(s.base);s.base = NULL;s.top = NULL;s.stacksize = 0;return OK;}Status ClearStack(SqStack &s){// 置空if (NULL == s.base)return ERROR;s.top = s.base;return OK;}Status StackEmpty(SqStack s){// 判空if (s.base == s.top)return TRUE;return FALSE;}int StackLength(SqStack s){// 长度if (NULL == s.base)return 0;return (int)(s.top - s.base);}Status GetTop(SqStack s, SElemType &e){// 返回栈顶元素if (s.base == s.top)return ERROR;e = *(s.top - 1);return OK;}Status Push(SqStack &s, SElemType e){// 入栈if (NULL == s.base)return ERROR;if (s.top - s.base >= s.stacksize){// 栈满s.base = (SElemType *)realloc(s.base, (s.stacksize + STACKINCREMENT) * sizeof(SElemType));if (!s.base)exit(OVERFLOW);s.top = s.base + s.stacksize;s.stacksize += STACKINCREMENT;}*s.top++ = e;return OK;}Status Pop(SqStack &s, SElemType &e){// 出栈if (NULL == s.base || s.top == s.base)return ERROR;e = * --s.top; // 出栈顶指针先自减，再赋值return OK;}Status StackTraverse(SqStack s, void(visit)(SElemType)){// 遍历SElemType *p = s.base;if (NULL == s.base)return ERROR;while (p < s.top)visit(*p++);printf("\n");return OK;}void visit(SElemType e){printf("%d ", e);}int main(int argc, char const *argv[]){SqStack s;cout << "InitStack" << endl;InitStack(s);cout << "StackEmpty" << endl;StackEmpty(s) ? cout << "yes\n" : cout << "no\n";cout << "Push" << endl;for (int i = 1; i <= 6; i++)Push(s, 2 * i);cout << "StackTraverse" << endl;StackTraverse(s, visit);cout << "StackLength" << endl;cout << StackLength(s);cout << "Pop" << endl;SElemType e;Pop(s, e);cout << e << endl;StackTraverse(s, visit);cout << "GetTop" << endl;GetTop(s, e);cout << e << endl;cout << "ClearStack" << endl;cout << "Before: ";StackEmpty(s) ? cout << "yes\n" : cout << "no\n";ClearStack(s);cout << "After: ";StackEmpty(s) ? cout << "yes\n" : cout << "no\n";cout << "DestoryStack" << endl;cout << "Before : ";s.base != NULL && s.top != NULL ? cout << "YES\n" : cout << "NO\n";DestoryStack(s);cout << "After: ";s.base != NULL && s.top != NULL ? cout << "YES\n" : cout << "NO\n";return 0;}

进制转换

行编辑器

#include <bits/stdc++.h>#define MaxSize 100#define SElemType char#define Status int#define ERROR 0#define OK 1#define INFEASIBLE -1#define TRUE 1#define FALSE 0using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct {SElemType *base;SElemType *top;int stacksize;}SqStack;Status InitStack(SqStack &s){s.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (NULL == s.base) exit(OVERFLOW);s.top = s.base;s.stacksize = STACK_INIT_SIZE;return OK;}Status Push(SqStack &s, SElemType e){if (NULL == s.base) return ERROR;if (s.top - s.base >= s.stacksize){s.base = (SElemType *)realloc(s.base,(s.stacksize + STACKINCREMENT) * sizeof(SElemType));if (NULL == s.base) exit(OVERFLOW);s.top = s.base + s.stacksize;s.stacksize += STACKINCREMENT;}*s.top++ = e;return OK;}Status DestoryStack(SqStack &s){free(s.base);s.top = NULL;s.base = NULL;s.stacksize = 0;return OK;}Status ClearStack(SqStack &s){if (s.base == s.top) return ERROR;s.top = s.base;return OK;}Status Pop(SqStack &s, SElemType &e){if (NULL == s.base || s.top == s.base) return ERROR;e = *-- s.top;return OK;}Status StackTraverse(SqStack s, void(visit)(SElemType)){SElemType *p = s.base;if (NULL == s.base)return ERROR;while (p < s.top)visit(*p++);printf("\n");return OK;}void visit(SElemType e){cout << e;}void LineEdit(){// 利用字符栈s，从终端接收一行并传送至调用过程的数据区SqStack s;char ch, c;InitStack(s);ch = getchar();while (ch != EOF){while (ch != EOF && ch != '\n'){switch(ch){case '#' : Pop(s, c); break;case '@' : ClearStack(s); break;default : Push(s, ch); // 有效字符进栈break;}ch = getchar();}ClearStack(s);if (ch != EOF) ch = getchar();}StackTraverse(s, visit);DestoryStack(s);}int main(int argc, char const *argv[]){LineEdit();return 0;}

未完待续。。。

本内容不代表本网观点和政治立场，如有侵犯你的权益请联系我们处理。

网友评论

网友评论仅供其表达个人看法，并不表明网站立场。