本文主要是介绍单链表的建立,测长,打印,删除,插入,排序,逆置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//单链表结构体
typedef struct student
{
int data;
struct student *next;
}node;
//建立单链表
node *create()
{
node *head,*p,*s;
int x,cycle=1;
head=(node*) malloc ( sizeof (node)); //建立头节点 p=head; while (cycle) { printf ( "\nPlease input the data:" ); scanf ( "%d" ,&x); if (x!=0) { s=(node*) malloc ( sizeof (node)); //每次新建一个节点 s->data=x; printf ( "\n%d" ,s->data); p->next=s; p=s; } else { cycle=0; } } head=head->next; p->next=NULL; printf ( "\n yyy %d" ,head->data); return (head); } //单链表测长 int length(node *head) { int n=0; node *p; p=head; while (p!=NULL) { p=p->next; n++; } return (n); } //单链表打印 void print(node *head) { node *p; int n; n=length(head); printf ( "\nNow,These %d records are :\n" ,n); p=head; if (head!=NULL) p=p->next; while (p!=NULL) { printf ( "\n uuu %d " ,p->data); p=p->next; } } 2、编程实现单链表删除节点。
解析：如果删除的是头节点，如下图：
则把head指针指向头节点的下一个节点。同时free p1，如下图所示：
如果删除的是中间节点，如下图所示：
则用p2的next指向p1的next同时，free p1 ，如下图所示：
//单链表删除节点 node * remove (node *head , int num) { node *p1,*p2; p1=head; while (num!=p1->data && p1->next!=NULL) //查找data为num的节点 { p2=p1; p1=p1->next; } if (num==p1->data) //如果存在num节点，则删除 { if (p1==head) { head=p1->next; free (p1); } else { p2->next=p1->next; } } else { printf ( "\n%d could not been found" ,num); } return (head); } 3、编写程序实现单链表的插入。
解析：单链表的插入，如下图所示：
如果插入在头结点以前，则p0的next指向p1，头节点指向p0，如下图所示：
如果插入中间节点，如下图所示：
则先让p2的next指向p0，再让p0指向p1，如下图所示：
如果插入尾节点，如下图所示：
则先让p1的next指向p0，再让p0指向空，如下图所示：
//单链表插入节点 node *insert(node *head, int num) { node *p0,*p1,*p2; p1=head; p0=(node *) malloc ( sizeof (node)); p0->data=num; while (p0->data > p1->data && p1->next!=NULL) { p2==p1; p1=p1->next; } if (p0->data<=p1->data) { if (head==p1) { p0->next=p1; head=p0; } else { p2->next=p0; p0->next=p1; } } else { p1->next=p0; p0->next=NULL; } return (head); } 4、编程实现单链表的排序。
答案：
- //单链表排序
- node *sort(node *head)
- {
- node *p,*p2,*p3;
- int n;
- int temp;
- n=length(head);
- if(head==NULL ||head->next==NULL)//如果只有一个或者没有节点
- return head;
- p=head;
- for(int j=1;j<n;++j)
- {
- p=head;
- for(int i=0;i<n-j;++i)
- {
- if(p->data > p->next->data) //每趟排序都把最大的数放到最后
- {
- temp=p->data;
- p->data=p->next->data;
- p->next->data=temp;
- }
- p=p->next;
- }
- }
- return (head);
- }
//单链表排序
node *sort(node *head)
{
node *p,*p2,*p3;
int n;
int temp;
n=length(head);
if(head==NULL ||head->next==NULL)//如果只有一个或者没有节点
return head;
p=head;
for(int j=1;j<n;++j)
{
p=head;
for(int i=0;i<n-j;++i)
{
if(p->data > p->next->data) //每趟排序都把最大的数放到最后
{
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
}
p=p->next;
}
}
return (head);
}5、编写实现单链表的逆置。
解析：单链表模型如下图所示：
进行单链表逆置，首先要让p2的next指向p1，如下图所示：
再由p1指向p2，p2指向p3，如下图所示：
让后重复p2的next指向p1，p1指向p2，p2指向p3。
- //单链表逆置
- node *reverse(node *head)
- {
- node *p1,*p2,*p3;
- if(head==NULL || head->next==NULL)
- return head;
- p1=head;
- p2=p1->next;
- while(p2)
- {
- p3=p2->next;
- p2->next=p1;
- p1=p2;
- p2=p3;
- }
- head->next=NULL;
- head=p1;
- return head;
- }
//单链表逆置
node *reverse(node *head)
{
node *p1,*p2,*p3;
if(head==NULL || head->next==NULL)
return head;
p1=head;
p2=p1->next;
while(p2)
{
p3=p2->next;
p2->next=p1;
p1=p2;
p2=p3;
}
head->next=NULL;
head=p1;
return head;
}6、编程实现删除单链表的头元素。
答案：
//删除单链表的头元素voidRemoveHead(node *head){node *p;p=head;head=head->next;free(p);}
7、给出一个单链表，不知道节点N的值，怎么只遍历一次就可以求出中间节点，写出算法。
解析：设立两个指针，比如*p和*q。p每次移动两个位置，即p=p->next->next，q每次移动一个位置，即q=q->next。当p达到最后一个节点时，q就是中间节点了。
答案：
//给出一个单链表，不知道节点N的值，怎么只遍历一次就可以求出中间节点voidsearchmid(node *head,node *mid){node *p,*q;p=head;q=head;while(p->next->next!=NULL){p=p->next->next;q=q->next;mid=q;}}
8、给定一个单向链表，设计一个时间优化并且空间优化的算法，找出该链表的倒数第m个元素。实现您的算法，注意处理相关的出错情况。m定义为当m=0时，返回链表最后一个元素。
解析：这是一个难题，我们需要的是倒数第m个元素，所以如果我们从某个元素开始，遍历了m个元素之后刚好到达链表末尾，那么这个元素就是要找的元素。也许从链表的尾部倒推回去不是最好的办法，那么我们可以从链表头开始计数。
思路一：我们可以先一次遍历求出链表的总长度n，然后顺序变量求出第n-m个元素，那么这个就是我们要找的元素了。
思路二：我们用两个指针，一个当前位置指针p和一个指向第m个元素的指针q，需要确保两个指针之间相差m个元素，然后以同样的速度移动它们，如果当q到达链表末尾时，那么p指针就是指向倒数第m个元素了。
答案：
//思路一node *searchLastElement1(node *head,intm){if(head==NULL)returnNULL;node *p=head;intcount=0;while(p!=NULL){p=p->next;count++;}if(count<m)returnNULL;p=head;for(inti=0;i<count-m;i++){p=p->next;}returnp;}//思路二node *searchLastElement2(node *head,intm){if(head==NULL)returnNULL;node *p,*q;p=head;for(inti=0;i<m;i++){if(p->next!=NULL){p=p->next;}else{returnNULL;}}q=head;while(p->next!=NULL){p=p->next;q->next;}returnq;}
这篇关于单链表的建立,测长,打印,删除,插入,排序,逆置的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
