这个是链表的实验代码
#include <stdio.h>
#include <stdlib.h>
#define ElementType int
typedef struct node {
ElementType data;
struct node *next;
} node;
typedef node* List;
int getLinkListLength(List L, int isCircleLinkList);
// 创建链表
List createALinkList(int n, int *isCircleLinkList) {
ElementType data;
List L = NULL, last;
node *p;
for (int i = 1; i <= n; i++) {
p = (node*)malloc(sizeof(node));
scanf("%d", &data);
p->data = data;
p->next = NULL;
if (!L) {
L = p;
last = L;
} else {
last->next = p;
last = last->next;
}
}
*isCircleLinkList = 0;
return L;
}
// 查找元素
int findNode(List L, int isCircleLinkList) {
ElementType data;
scanf("%d", &data);
List last = L;
while (last) {
if (last->data == data) {
printf("找到了\n");
return 0;
}
last = last->next;
if(last == L && isCircleLinkList) break;
}
printf("找不到\n");
return 1;
}
// 插入元素到指定位置
int insertNode(List *L, int isCircleLinkList) {
List last = isCircleLinkList? (*L)->next : *L;
node *p = (node*)malloc(sizeof(node));
ElementType data;
int insertPosition, i = 1, length = getLinkListLength(*L, isCircleLinkList)+1;
scanf("%d %d", &insertPosition, &data);
if (insertPosition > length) {
printf("发生越界!\n");
return 1;
}
p->data = data;
p->next = NULL;
while (last->next) {
if (i == insertPosition - 1 || insertPosition == 1) break;
last = last->next;
i++;
if(last == *L && isCircleLinkList) break;
}
if (insertPosition == 1) {
if(!isCircleLinkList) {
p->next = *L;
*L = p;
} else {
p->next = (*L)->next;
(*L)->next = p;
}
} else {
p->next = last->next;
last->next = p;
}
return 0;
}
// 读取链表
void readList(List L, int isCircleLinkList) {
List last = isCircleLinkList? L->next : L;
while (last) {
printf("%d ", last->data);
last = last->next;
if(last == L && isCircleLinkList) break;
}
printf("\n");
}
// 去除特定位置的元素
void removeNode(List *L, int isCircleLinkList) {
int rmPosition, i = 1;
node *p;
List last = *L;
scanf("%d", &rmPosition);
while (last->next && !isCircleLinkList) {
if (i == rmPosition - 1 || rmPosition == 1) break; // 将位置定位到前一个节点，如果要删除的节点是第一个，那就直接退出循环
last = last->next;
i++;
}
while(last->next && isCircleLinkList) {
if (i == rmPosition) break; // 将位置定位到前一个节点，如果要删除的节点是第一个，那就直接退出循环
last = last->next;
i++;
}
if (rmPosition == 1) {
if(isCircleLinkList) {
p = (*L)->next;
(*L)->next = (*L)->next->next;
} else {
p = *L;
*L = last->next;
}
free(p);
} else if (last->next && rmPosition-1 == i && !isCircleLinkList) {
p = last->next;
last->next = last->next->next;
free(p);
} else if(last->next != *L && isCircleLinkList && rmPosition == i) {
p = last->next;
last->next = last->next->next;
free(p);
} else {
printf("越界！\n");
}
}
// 转化为有头结点的循环链表
void makeIntoCircleLinkList(List *L, int *isCircleLinkList) {
List last = *L;
if(last == *L && *isCircleLinkList) return;
while (last->next) last = last->next;
last->next = (node*)malloc(sizeof(node));
last = last->next;
last->next = *L;
*L = last;
*isCircleLinkList = 1;
}
// 获取链表长度
int getLinkListLength(List L, int isCircleLinkList) {
int count = 0;
List last = isCircleLinkList? L->next : L;
while (last) {
count++;
last = last->next;
if(last == L && isCircleLinkList) break;
}
return count;
}
// 将某一元素插入有序表中
int insertANodeToALinkListInOrder(List *L, int isCircleLinkList) {
int state = 0;
node *last1 = isCircleLinkList? (*L)->next : *L, *last2 = isCircleLinkList? (*L)->next->next : (*L)->next;
while(last2) {
if(last1->data > last2->data) {
goto out;
}
last1 = last2;
last2 = last2->next;
if(last2 != *L && isCircleLinkList) break;
}
state = 1;
goto out3;
out:;
last1 = isCircleLinkList? (*L)->next : *L, last2 = isCircleLinkList? (*L)->next->next : (*L)->next;
while(last2) {
if(last1->data < last2->data) {
goto out1;
}
last1 = last2;
last2 = last2->next;
if(last2 != *L && isCircleLinkList) break;
}
state = 2;
out3:;
node *p = (node*)malloc(sizeof(node)), *k = NULL, *q = isCircleLinkList? (*L)->next : *L;
scanf("%d", &p->data);
while (q) {
if ((state == 1 && p->data < q->data) || (state == 2 && p->data > q->data)) break;
k = q;
q = q->next;
if(q == *L && isCircleLinkList) break;
}
if (!k) {
p->next = isCircleLinkList? (*L)->next : *L;
if(isCircleLinkList) (*L)->next = p;
else *L = p;
} else {
p->next = k->next;
k->next = p;
}
return state;
out1:;
printf("这不是有序表\n");
return state;
}
// 元素逆置
void f(List *L) {
List newL = NULL;
node *last = *L, *p = (*L)->next;
while (last) {
last->next = newL;
newL = last;
last = p;
if (p) p = p->next;
}
*L = newL;
}
// 合并两个有序链表
List mergeTwoLinkList(List *L1, List *L2) {
List pL1 = *L1, pL2 = *L2, L3 = NULL, pL3 = NULL;
while (*L1 && *L2) {
if (pL1->data < pL2->data) {
if (L3) {
pL1 = *L1;
*L1 = pL1->next;
pL1->next = pL3->next;
pL3->next = pL1;
pL3 = pL3->next;
} else {
L3 = pL1;
pL3 = L3;
*L1 = pL1->next;
}
pL1 = *L1;
} else {
if (L3) {
pL2 = *L2;
*L2 = pL2->next;
pL2->next = pL3->next;
pL3->next = pL2;
pL3 = pL3->next;
} else {
L3 = pL2;
pL3 = L3;
*L2 = pL2->next;
}
pL2 = *L2;
}
}
while (*L1) {
pL1 = *L1;
*L1 = pL1->next;
pL1->next = pL3->next;
pL3->next = pL1;
pL3 = pL3->next;
}
while (*L2) {
pL2 = *L2;
*L2 = pL2->next;
pL2->next = pL3->next;
pL3->next = pL2;
pL3 = pL3->next;
}
pL3->next = NULL;
return L3;
}
// 主函数
int main() {
int choose, isCircleLinkList = 0, count, n, isCircleLinkList1 = 0, isCircleLinkList2 = 0;
List L = NULL, L1, L2, L3;
while (1) {
printf("================menu===================\n");
printf("[1] 创建链表\n");
printf("[2] 查找元素\n");
printf("[3] 插入到指定位置元素\n");
printf("[4] 删除指定位置元素\n");
printf("[5] 转换为循环链表\n");
printf("[6] 获取链表长度\n");
printf("[7] 将元素插入到有序表中\n");
printf("[8] 元素逆置\n");
printf("[9] 两个有序链表的合并\n");
printf("请选择：");
scanf("%d", &choose);
switch (choose) {
case 1:
printf("从键盘输入10个整数，产生带表头的单链表，并输出结点值。\n");
L = createALinkList(10, &isCircleLinkList);
readList(L, isCircleLinkList);
break;
case 2:
printf("从键盘输入1个整数，在单链表中查找该结点。若找到，则显示“找到了”；否则，则显示“找不到”。\n");
if(L) findNode(L, isCircleLinkList);
else printf("当前链表不存在\n");
break;
case 3:
printf("从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。\n");
if(L) {
insertNode(&L, isCircleLinkList);
readList(L, isCircleLinkList);
} else printf("当前链表不存在\n");
break;
case 4:
printf("从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。\n");
if(L) {
removeNode(&L, isCircleLinkList);
readList(L, isCircleLinkList);
} else printf("当前链表不存在\n");
break;
case 5:
printf("把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。\n");
if(L) {
makeIntoCircleLinkList(&L, &isCircleLinkList);
readList(L, isCircleLinkList);
} else printf("当前链表不存在\n");
break;
case 6:
count = getLinkListLength(L, isCircleLinkList);
printf("The number of node in this link list is %d\n", count);
break;
case 7:
printf("把某个元素插入链表当中，输出链表所有结点值，观察输出结果。\n");
if(L) {
if(insertANodeToALinkListInOrder(&L, isCircleLinkList)) readList(L, isCircleLinkList);
} else {
printf("当前链表不存在\n");
}
break;
case 8:
if(L) f(&L);
else printf("当前链表不存在\n");
readList(L, isCircleLinkList);
break;
case 9:
printf("从键盘输入n，然后输入n个整数\n");
scanf("%d", &n);
L1 = createALinkList(n, &isCircleLinkList1);
printf("从键盘输入n，然后输入n个整数\n");
scanf("%d", &n);
L2 = createALinkList(n, &isCircleLinkList2);
L3 = mergeTwoLinkList(&L1, &L2);
readList(L3, isCircleLinkList);
break;
default:
goto out;
}
}
out:;
}
