声明:著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除,求表长、有序表插入、元素逆置、2个有序表合并等。
#include <stdio.h>
#include <stdlib.h>
//单链表的定义:
typedef int DataType; //DataType可以是任何相应的数据类型如int, float或char
typedef struct ListNode //结点类型定义
{ DataType data; //结点的数据域
struct ListNode *next; //结点的指针域
}ListNode;
typedef ListNode *LinkList;
//测试用例 1 2 3 4 5 6 7 8 9 10 -1
// 4 6 8 10 12 -1
int main()
{
int i,j;
DataType key,x;
LinkList head=NULL;
LinkList CreateList();
void PrintList(LinkList head);
int LocateNode(LinkList head,DataType key);
void InsertList(LinkList head,DataType x,int i);
void DeleteList(LinkList head,int i);
void ChangeCircList(LinkList head);
void PrintCircList(LinkList head);
void InsertOrderList(LinkList head,int x);
LinkList reverseList(LinkList head);
void MergeList_L(LinkList La,LinkList Lb,LinkList *Lc);
char choice;
while (1)
{
system("cls");
printf("\n\n\n\n");
printf("\t\t 链表操作 \n");
printf("\t\t======================================");
printf("\n\n");
printf("\t\t 1:建立单链表 \n");
printf("\t\t 2:显示单链表 \n");
printf("\t\t 3:查找 \n");
printf("\t\t 4:插入 \n");
printf("\t\t 5:删除 \n");
printf("\t\t 6:改为循环单链表并显示 \n");
printf("\t\t 7:有序表插入 \n");
printf("\t\t 8:元素逆置 \n");
printf("\t\t 9:2个有序表合并 \n");
printf("\n");
printf("\t\t 0:退出 \n");
printf("\n");
printf("\t\t请选择:");
choice = getchar();
system("cls");
switch(choice)
{
case '1':
printf("输入单链表:");
head=CreateList();
printf("链表创建成功!\n");
getchar();/*第一个getchar会接收到上面createList函数中scanf最后敲击的回车
所以后面再加一个,这样系统才会等待下一个字符进入,才能看得到东西 */
getchar();
break;
case '2':
PrintList(head);
getchar();
getchar();
break;
case '3':
printf("输入要查找的值:");
scanf("%d",&key);
j=LocateNode(head,key); //单链表查找
printf("要查找的值在第%d个\n",j);
getchar();
getchar();
break;
case '4':
printf("请输入欲插入元素的位置:");
scanf("%d",&i);
printf("请输入欲插入的元素:");
scanf("%d",&x);
InsertList(head,x,i); //单链表插入
PrintList(head); //输出顺序表
getchar();
getchar();
break;
case '5':
printf("请输入欲删除结点的位置:");
scanf("%d",&i);
DeleteList(head,i); //单链表删除
PrintList(head); //输出顺序表
getchar();
getchar();
break;
case '6':
ChangeCircList(head); //修改为循环单链表
printf("改为循环单链表成功:\n");
PrintCircList(head); //输出循环单链表
getchar();
getchar();
break;
case '7':
printf("请输入欲插入有序表的元素:");
scanf("%d",&x);
InsertOrderList(head,x);
PrintList(head);
getchar();
getchar();
break;
case '8':
head=reverseList(head);
printf("逆置成功\n");
PrintList(head);
getchar();
getchar();
break;
case '9':
printf("输入要被合并的顺序表:");
LinkList Lb;
LinkList Lc;
Lb=CreateList();
printf("链表创建成功!\n");
MergeList_L(head,Lb,&Lc);
printf("顺序表合并成功!\n");
PrintList(Lc);
getchar();
getchar();
break;
case '0':
exit(0);
}
}
}
LinkList CreateList()
{
int num;
int head_data;
struct ListNode *s, *r, *h = (struct ListNode *)malloc(sizeof(struct ListNode));
scanf("%d", &head_data);
h->data = head_data;
r = h; /* 尾指针初值指向头结点 */
scanf("%d", &num);
while (num != -1)
{
s = (struct ListNode *)malloc(sizeof(struct ListNode)); /* 生成新结点*/
if (s == NULL)
{
printf("内存分配失败\n");
exit(-1);
}
s->data = num;
r->next = s;
r = s;
scanf("%d", &num); // 更新输入的 num 值
}
r->next = NULL;
return h; /* 返回头指针 */
}
//单链表的输出:
void PrintList(LinkList head)
{
int c=0;
LinkList cur;
if (head != NULL)
cur = head;
else{
printf("no node");
return;
};
while (cur != NULL){
printf("%d ", cur->data);
c++;
cur = cur->next;
}
printf("\n现在表长为:%d", c);
return;
}
//单链表的查找:
int LocateNode(LinkList head,DataType key)
{
int c=1;
ListNode *p=head;//->next; /* 从开始结点比较 */
while (p&&p->data!=key){ /* 直到 p 为 NULL 或 p->data 是 key为止 */
p=p->next; /* 扫描下一结点 */
c++;}
return c;
}
//单链表的插入:
void InsertList(LinkList head,DataType x,int i)
{
ListNode *p=head,*s;
int j=0;
int c=2;/* 寻找第 i-1 个结点 */
while (p&&c<i){ /* 直到 p 为 NULL 或 p->data 是 key为止 */
p=p->next; /* 扫描下一结点 */
c++;
}
if(p==NULL){
printf(" 插入位置非法 \n");
exit(0);
}
s=(LinkList)malloc(sizeof(ListNode));
s->data=x;
s->next=p->next;
p->next=s;
}
//单链表的删除:
void DeleteList(LinkList head,int i)
{
ListNode *p=head,*q;
int c=2;/* 寻找第 i-1 个结点 */
while (p&&c<i){ /* 直到 p 为 NULL 或 p->data 是 key为止 */
p=p->next; /* 扫描下一结点 */
c++;
}
if(p==NULL||p->next==NULL){
printf(" 删除位置非法 \n");
exit(0);
}
q=p->next; // 临时保存被删结点的地址以备释放
p->next=q->next; // 改变删除结点前驱结点的指针域
free(q); // 释放删除结点的空间
}
//修改为循环单链表:
void ChangeCircList(LinkList head)
{
ListNode *p=head;//->next; /* 从开始结点比较 */
while (p->next)/* 直到 p->next 为 NULL是 key为止 */
p=p->next; /* 扫描下一结点 */
p->next=head;
}
//循环单链表的输出:
void PrintCircList(LinkList head)
{
LinkList cur;
int c=0;
if (head != NULL)
cur = head;
else{
printf("no node");
return;
};
while (cur->next != head){
printf("%d ", cur->data);
cur = cur->next;
c++;
}
printf("%d ", cur->data);
c++;
printf("\n现在表长为:%d ", c);
return;
}
void InsertOrderList(LinkList head,int x)
{
ListNode *p=head,*s;
int j=0;
while (p->data<x){
p=p->next; /* 扫描下一结点 */
}
s=(LinkList)malloc(sizeof(ListNode));
s->data=x;
s->next=p->next;
p->next=s;
}
LinkList reverseList(LinkList head)
{
if (head == NULL || head->next == NULL) {
return head;
}
// 例:1->2->3->4->5-null,从 if 递归出口返回时 newHead = 5, head = 4(递归特点:谁调用返回给谁)
LinkList newHead =reverseList(head->next);
// head = 4, newHead = 5, head.next.next = 4.next.next = 5.next = 4
head->next->next = head;
// 避免链表成环,5->4->null
head->next = NULL;
// 返回新的头节点
return newHead;
}
void MergeList_L(LinkList La, LinkList Lb, LinkList *Lc) { // 修改参数类型,
LinkList pa = La;
LinkList pb = Lb;
LinkList pc;
if (La->data < Lb->data) {
pc = La;
*Lc = La;
pa = La->next;
} else {
pc = Lb;
*Lc = Lb;
pb = Lb->next;
}
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 != NULL ? pa : pb; // 插入剩余段
//free(Lb);
}
四、运行输出结果:
LinkList CreateList();
输入单链表:1 2 3 4 5 6 7 8 9 10 -1
链表创建成功!
void PrintList(LinkList head);
1 2 3 4 5 6 7 8 9 10
现在表长为:10
int LocateNode(LinkList head,DataType key);
输入要查找的值:5
要查找的值在第5个
void InsertList(LinkList head,DataType x,int i);
请输入欲插入元素的位置:2
请输入欲插入的元素:4
1 4 2 3 4 5 6 7 8 9 10
现在表长为:11
void DeleteList(LinkList head,int i);
请输入欲删除结点的位置:2
1 2 3 4 5 6 7 8 9 10
现在表长为:10
void ChangeCircList(LinkList head);void PrintCircList(LinkList head);
改为循环单链表成功:
1 2 3 4 5 6 7 8 9 10
现在表长为:10
void InsertOrderList(LinkList head,int x);
请输入欲插入有序表的元素:4
1 2 3 4 4 5 6 7 8 9 10
现在表长为:11
LinkList reverseList(LinkList head);
逆置成功
10 9 8 7 6 5 4 3 2 1
现在表长为:10
void MergeList_L(LinkList La,LinkList Lb,LinkList *Lc);
输入要被合并的顺序表:4 6 8 10 12 -1
链表创建成功!
顺序表合并成功!
1 2 3 4 4 5 6 6 7 8 8 9 10 10 12
现在表长为:15
运行输出结果:
LinkList CreateList();
输入单链表:1 2 3 4 5 6 7 8 9 10 -1
链表创建成功!
void PrintList(LinkList head);
1 2 3 4 5 6 7 8 9 10
现在表长为:10
int LocateNode(LinkList head,DataType key);
输入要查找的值:5
要查找的值在第5个
void InsertList(LinkList head,DataType x,int i);
请输入欲插入元素的位置:2
请输入欲插入的元素:4
1 4 2 3 4 5 6 7 8 9 10
现在表长为:11
void DeleteList(LinkList head,int i);
请输入欲删除结点的位置:2
1 2 3 4 5 6 7 8 9 10
现在表长为:10
void ChangeCircList(LinkList head);void PrintCircList(LinkList head);
改为循环单链表成功:
1 2 3 4 5 6 7 8 9 10
现在表长为:10
void InsertOrderList(LinkList head,int x);
请输入欲插入有序表的元素:4
1 2 3 4 4 5 6 7 8 9 10
现在表长为:11
LinkList reverseList(LinkList head);
逆置成功
10 9 8 7 6 5 4 3 2 1
现在表长为:10
void MergeList_L(LinkList La,LinkList Lb,LinkList *Lc);
输入要被合并的顺序表:4 6 8 10 12 -1
链表创建成功!
顺序表合并成功!
1 2 3 4 4 5 6 6 7 8 8 9 10 10 12
现在表长为:15
标签:10,head,单链,int,代码,next,LinkList,printf,C语言 From: https://blog.csdn.net/skhoole/article/details/137571590