实验内容：
首先建立一个带或不带头结点的单链表（n个结点，每个结点值由键盘输入），然后对该单链表进行相应操作，实现以下1~6中之一算法，并输出各种操作的结果：
1、用单链表作为存储结构，实现线性表（a0,a1,…, an-1）就地逆置的操作，所谓就地指辅助空间应为O(1)。
2、设单链表L是一个递减有序表，试写一算法将X插入其中后仍保持L的有序性。
3、写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
4、设计一个算法，对单链表按结点值从小到大对结点进行排序。
5、设计一个算法，将两个有序单链表合并成一个有序的单链表。
6、设计一个算法，求两个单链表表示的集合的交集，并将结果用一个新的单链表保存并返回。
一、链表任务开始前的基础代码：
1、弄个结构体
2、创建链表函数（带头节点的链表）
3、创建结点函数
4、插入结点函数
5、打印链表
附加：结点删除就不写了啊，因为老师安排的任务用不着删除
#include#include #include typedef struct stu { int data; struct stu* next; }Node; //创建链表 Node* createList() { Node* headNode=(Node*)malloc(sizeof(Node)); headNode->next=NULL; return headNode; } //创建结点 Node* createNode(int data) { Node* newNode=(Node*)malloc(sizeof(Node)); newNode->data=data; newNode->next=NULL; return newNode; } //尾插 void InsByTail(Node* headNode,int data) { Node* newNode=createNode(data); while(headNode->next) { headNode=headNode->next; } newNode->next=headNode->next; headNode->next=newNode; } int DelByAppoint(Node* headNode,int da) { while(headNode->next->data!=da) { headNode=headNode->next; if(headNode->next==NULL) { printf("为找到要删除数据n"); return 0; } } headNode->next=headNode->next->next; return 1; } //打印链表 int printList(Node* headNode) { Node* pMove=headNode->next; if(pMove==NULL) { printf("链表为空n"); return 0; } while(pMove) { printf("%dt",pMove->data); pMove=pMove->next; } printf("n"); return 1; }
二、单链表逆置操作
用单链表作为存储结构，实现线性表（a0,a1,…, an-1）就地逆置的操作，所谓就地指辅助空间应为O(1)。
思想：
1、原链表地址的next存给p(因为是带头节点的所以用next)
2、原链表置空
3、q再存放p地址
4、p移动到下一个结点
5、再把q结点头插法插入到headNode中
6、循环执行直到p为空结束
Node *reverseList(Node *headNode)
{
Node *p, *q;
p = headNode->next;
headNode->next = NULL;
while (p != NULL)
{
q = p;
p = p->next;
q->next = headNode->next;
headNode->next = q;
}
return headNode;
}
三、插入数据后链表依旧有序实现
设单链表L是一个递减有序表，试写一算法将X插入其中后仍保持L的有序性。
思想：
1、while循环找
2、找到了执行插入操作
3、没找到跳出循环后那就一定是最小的数据直接在尾部插入
int InsByAppoint(Node* node,int data) //node为有序的递减有序表
{
Node* newNode=createNode(data);
while(node->next)
{
if(node->next->data<=newNode->data)
{
newNode->next=node->next;
node->next=newNode;
return 1;
}
node=node->next;
}
if(node->next==NULL) //插入数据为表中最小情况
{
newNode->next=node->next;
node->next=newNode;
return 1;
}
}
四、删除相同数据
写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
思想：
1、定义个数组把链表数据全存放到数组中
2、数组数据之间删除重复数据
下标为 i 的和下标为 j 的比较找到相同的了，下标为 j 以后的数组数据全向前移动
移动完成以后总长度 -1
下次比较的 j 的下表也要 -1 不然再往后找的话就跳过了一个
3、再把数组数据插入到原来链表实现删除重复数据
Node* Delsame(Node* L)
{
int a[1000]={0},n=0,i=0,j=0,k=0;
Node* p=createList();
p=L->next;
while(p)
{
a[n++]=p->data;
p=p->next;
}
for(i=0;inext=NULL;
for(i=0;i
五、链表数据从小到大排序
设计一个算法，对单链表按结点值从小到大对结点进行排序。
思想：
1、同上差不多把数据放到数组中来
2、用个快速排序实现数组数据从小到大排序
3、把数据重新插入到链表中去
//快排
void quick_sort(int p[],int l,int r)
{
if(l>=r) return;
int i,j,x;
x=p[l];
i=l-1;
j=r+1;
while(ix);
if(inext;
while(p)
{
a[n++]=p->data;
p=p->next;
}
quick_sort(a,0,n-1);
L->next=NULL;
for(i=0;i
六、合并
设计一个算法，将两个有序单链表合并成一个有序的单链表。
思想：
1、while循环判断俩是否走到空了走到了结束
2、if比较大小，小的用插入函数插进去
3、while循环结束后还需要判断是否数据插完了没
4、俩while循环判断呢俩指针是否走到空了
5、没走到接着插直到走完
void combine(Node* L1,Node* L2)
{
Node* L3=createList();
Node* pMove1=L1->next;
Node* pMove2=L2->next;
while(pMove1&&pMove2)
{
if(pMove1->datadata)
{
InsByTail(L3,pMove1->data);
pMove1=pMove1->next;
}
else
{
InsByTail(L3,pMove2->data);
pMove2=pMove2->next;
}
}
while(pMove1)
{
InsByTail(L3,pMove1->data);
pMove1=pMove1->next;
}
while(pMove2)
{
InsByTail(L3,pMove2->data);
pMove2=pMove2->next;
}
printList(L3);
}
七、找俩链表相同数据
设计一个算法，求两个单链表表示的集合的交集，并将结果用一个新的单链表保存并返回。
思想：
1、 直接简单的双重while循环比较
2、找到相同的用插入函数插入进去
3、第二个循环走完后得重置一下p2这个指针，然后p1指针走到下一个结点
4、最后返回一下呢个存放相同数据的结点啊
Node* fun(Node* L1,Node* L2)
{
Node* L3=createList();
Node* p1=L1->next;
Node* p2=L2->next;
while(p1)
{
while(p2)
{
if(p1->data==p2->data)
{
InsByTail(L3,p1->data);
}
p2=p2->next;
}
p1=p1->next;
p2=L2->next; //p2走到空了，所以重新设置为原来值
}
return L3;
}
逐渐暴躁中...............................................................
