|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
《数据结构/严蔚敏》代码 2016/10/22/更新
http://program.bbs.am/viewthread.php?tid=159434&fromuid=1
- #include<stdio.h>
- #include<stdlib.h>
- #define INIT_SIZE 5
- #define INCREMENT 1
- #define OK 1
- #define ERROR 0
- #define OVERFLOW -1
- #define FUNCTIONNUMS 5
- typedef int ElemType;
- typedef int Status;
- typedef struct {
- ElemType *elem; //存储空间基址
- int length; //当前长度
- int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
- }SqList;
- Status InitList_Sq(SqList &L) {
- L.elem = (ElemType *)malloc(sizeof(ElemType)*INIT_SIZE); //给L.elem分配地址
- if (!L.elem) exit(OVERFLOW); //存储分配失败
- L.length = 0; //空表长度为0
- L.listsize = INIT_SIZE; //初始存储容量
- return OK;
- }// InitList_Sq
- Status ListInsert_Sq(SqList &L, int i, ElemType e) {
- //在顺序线性表中第i个位置之前插入新的元素e
- ElemType *newbase, *q, *p;
- if (i<1 || i>L.length + 1) return ERROR; //i的值不合法
- if (L.length >= L.listsize) {//当前存储空间已满,增加分配
- newbase = (ElemType *)realloc(L.elem, (L.listsize + INCREMENT)*sizeof(ElemType));
- if (!newbase) exit(OVERFLOW);//存储分配失败
- L.elem = newbase; //新基址
- L.listsize += INCREMENT;//增加存储容量
- }
- q = &(L.elem[i - 1]);
- for (p = &(L.elem[L.length - 1]);p >= q;--p) {
- *(p + 1) = *p;
- }//插入位置及之后的元素右移
- *q = e;//插入e
- ++L.length;//表长增1
- return OK;
- }// ListInsert_Sq
- Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
- //在顺序线性表L中删除第i个元素,并用e返回其值
- //i的合法值为1<=i<=ListLength_Sq(L)
- ElemType *q, *p;
- if (i<1 || i>L.length) return ERROR;//i值不合法
- q = &L.elem[i - 1];//p为被删除元素的位置
- e = *q;//被删除元素的值赋给e
- p = L.elem + L.length - 1;//表尾元素的位置
- for (++q;p >= q;++q) *(q - 1) = *q;//被删除元素之后的元素左移
- --L.length;//表长减1
- return OK;
- }
- void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) {
- ElemType *pa, *pb, *pc;
- pa = La.elem;
- pb = Lb.elem;
- Lc.listsize = Lc.length = La.length + Lb.length;
- pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));
- if (!Lc.elem) exit(OVERFLOW);//存储分配失败
- while ((pa <= La.elem + La.length - 1) && (pb <= Lb.elem + Lb.length - 1)) {//并归
- if (*pa <= *pb) *pc++ = *pa++;
- else *pc++ = *pb++;
- }
- while (pa <= La.elem + La.length - 1) *pc++ = *pa++;//插入La的剩余元素
- while (pb <= Lb.elem + Lb.length - 1) *pc++ = *pb++;//插入Lb的剩余元素
- }
- typedef struct LNode {
- ElemType data;
- struct LNode *next;
- }LNode, *LinkList;
- void CreateList_L(LinkList &L, int n) {//尾插法
- LinkList p, r;
- int i;
- L = (LinkList)malloc(sizeof(LNode));
- r = L;
- L->next = NULL;
- for (i = 0;i<n;i++) {
- p = (LinkList)malloc(sizeof(LNode));
- p->next = NULL;
- scanf("%d", &p->data);
- r->next = p;
- r = p;
- }
- }
- Status GetElem_L(LinkList &L, int i, ElemType &e) {
- LinkList p;
- int j = 1;
- p = L->next;
- while (p&&j<i) {
- p = p->next;
- ++j;
- }
- if (!p || j>i)return ERROR;
- e = p->data;
- return OK;
- }
- Status ListDelete_L(LinkList &L, int i, ElemType &e) {
- LinkList p = L, q;
- int j = 0;
- while (p->next&&j<i - 1) {
- p = p->next;
- j++;
- }
- if (!(p->next) || j>i - 1) return ERROR;
- q = p->next;
- p->next = q->next;
- e = q->data;
- free(q);
- return OK;
- }
- void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
- LinkList pa = La->next, pb = Lb->next, pc;
- Lc = pc = La;
- 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);
- }
- typedef struct Stack {
- ElemType *base;
- ElemType *top;
- int stacksize;
- }Stack;
- Status InitStack(Stack &S) {
- S.base = S.top = (ElemType *)malloc(sizeof(ElemType)*INIT_SIZE);
- if (!S.base)exit(OVERFLOW);
- S.stacksize = INIT_SIZE;
- return OK;
- }
- Status PushStack(Stack &S, ElemType e) {
- if ((S.top - S.base) >= S.stacksize) {
- S.base = (ElemType *)realloc(S.base, sizeof(ElemType)*(S.stacksize + INCREMENT));
- if (!S.base)exit(OVERFLOW);
- S.top = S.base + S.stacksize;
- S.stacksize += INCREMENT;
- }
- *S.top = e;
- S.top++;
- return OK;
- }
- Status PopStack(Stack &S, ElemType &e) {
- if (S.top == S.base)return ERROR;
- e = *(S.top - 1);
- --S.top;
- return OK;
- }
- Status GetTop(Stack S, ElemType &e) {
- if (S.top == S.base)return ERROR;
- e = *(S.top - 1);
- return OK;
- }
- int main()
- {
- int n, i, j;
- ElemType e;
- printf("-----------数据结构------------\n");
- while (1) {//循环所有功能
- printf("功能:\n1、顺序表的初始化、插入以及删除\n2、顺序表的合并\n3、单链表的创建、查找以及删除\n4、单链表的合并\n5、栈的初始化、获取栈顶元素、删除栈顶元素以及增加栈元素\n");
- printf("-------------------------------\n");
- printf("请选择功能:");
- scanf("%d", &n);
- do {
- if (n>FUNCTIONNUMS) {
- printf("\n功能输入错误,请重新输入:");
- scanf("%d", &n);
- }
- } while (n>FUNCTIONNUMS);
- printf("-----------功能:%d-------------\n", n);
- switch (n) {
- case 1: {
- SqList L;
- printf("请初始化顺序表:");
- InitList_Sq(L);
- for (j = 0;j<INIT_SIZE;j++) {
- scanf("%d", L.elem + j);
- L.length++;
- }
- printf("请输入您要插入的位置以及数据,并用“ ”隔开:");
- scanf("%d%d", &i, &e);
- ListInsert_Sq(L, i, e);
- printf("插入后的数据为:");
- for (j = 0;j<L.length;j++) {
- printf("%d ", *(L.elem + j));
- }
- printf("\n");
- printf("请输入您要删除的位置:");
- scanf("%d", &i);
- if (ListDelete_Sq(L, i, e)) {
- printf("删除成功!\n删除的数据为:%d\n", e);
- printf("删除后的数据为:");
- for (j = 0;j<L.length;j++) {
- printf("%d ", *(L.elem + j));
- }
- }
- else printf("删除失败!\n请检查删除位置是否有误!");
- printf("\n");
- break;
- }
- case 2: {
- SqList La, Lb, Lc;
- printf("请初始化顺序表1:");
- InitList_Sq(La);
- for (j = 0;j<La.listsize;j++) {
- scanf("%d", La.elem + j);
- La.length++;
- }
- printf("请初始化顺序表2:");
- InitList_Sq(Lb);
- for (j = 0;j<Lb.listsize;j++) {
- scanf("%d", Lb.elem + j);
- Lb.length++;
- }
- MergeList_Sq(La, Lb, Lc);
- printf("合并后的顺序表为:");
- for (j = 0;j<Lc.length;j++) {
- printf("%d ", *(Lc.elem + j));
- }
- printf("\n");
- break;
- }
- case 3: {
- LinkList L, p;
- int i;
- printf("请初始化单链表:");
- CreateList_L(L, INIT_SIZE);
- printf("请问要查找第几个数据:");
- scanf("%d", &i);
- if (GetElem_L(L, i, e)) {
- printf("查找成功!\n");
- printf("第%d个数据为:%d\n", i, e);
- }
- else printf("查找失败!请检查输入是否有误!\n");
- printf("请输入您要删除的位置:");
- scanf("%d", &i);
- if (ListDelete_L(L, i, e)) {
- p = L;
- printf("删除成功!\n删除的数据为:%d\n", e);
- printf("删除后的数据为:");
- while (p->next) {
- p = p->next;
- printf("%d ", p->data);
- }
- }
- else printf("删除失败!\n请检查删除位置是否有误!");
- printf("\n");
- break;
- }
- case 4: {
- LinkList La, Lb, Lc, p;
- printf("请初始化单链表1:");
- CreateList_L(La, INIT_SIZE);
- printf("请初始化单链表2:");
- CreateList_L(Lb, INIT_SIZE);
- printf("合并后的单链表为:");
- MergeList_L(La, Lb, Lc);
- p = Lc->next;
- while (p) {
- printf("%d ", p->data);
- p = p->next;
- }
- break;
- }
- case 5: {
- Stack S;
- char ch;
- printf("请初始化栈:");
- InitStack(S);
- for (i = 1;i <= S.stacksize;i++) {
- scanf("%d", S.top);
- S.top++;
- }
- GetTop(S, e);
- printf("当前栈顶元素为:%d\n", e);
- printf("是否需要删除栈顶元素(Y/N)?");
- getchar();
- ch = getchar();
- if (ch == 'Y' || ch == 'y') {
- if (PopStack(S, e)) {
- printf("删除成功!\n删除的数据为:%d\n", e);
- printf("当前栈元素为:");
- for (i = 0;i<S.top - S.base;i++) {
- printf("%d ", *(S.base + i));
- }
- printf("\n");
- }
- else printf("删除失败!当前栈为空,无法删除!\n");
- }
- printf("是否需要增加栈元素(Y/N)?");
- getchar();
- ch = getchar();
- if (ch == 'Y' || ch == 'y') {
- printf("请输入需要增加的数据:");
- scanf("%d", &e);
- if (PushStack(S, e)) {
- printf("入栈成功!\n");
- printf("当前栈元素为:");
- for (i = 0;i<S.top - S.base;i++) {
- printf("%d ", *(S.base + i));
- }
- printf("\n");
- }
- else printf("入栈失败!内存空间不足!");
- }
- }
- }
- printf("\n-------------------------------\n");
- }
- return 0;
- }
复制代码 |
|