#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;
}
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2016-11-1 12:47:23
置顶卡
千斤顶
显身卡
楼主
发表于 2017-4-13 20:30:00