单链表的算法设计

当学习完单链表后，仔细回忆回忆，单链表还是很容易掌握的，但是还是要仔细认真的品味。

单链表可以看做是由若干个结点由指针指向后继结点一种表.
结点是由数据域和指针域构成。真正有效的存储是数据域,指针域负责指向下一个结点存储的位置,所以它的存储密度都是小于1,而之前学习的顺序表存储密度都是1.
那么如何定义结构体

12345

typedef struct {	Eletype data;	struct *next;//指针域}node,*Node;

那么单链表具体可以做些什么操作哪?

1. 初始化操作,主要是对于头结点来说的,头结点一般不存储数据

   12345

   void initnNode(Node head){ head=(Node)malloc(sizeof(node)); head->next=null;}

2. 插入结点操作,插入分为两种,头插法和尾插法

   1234567891011121314151617

   void insertData(Node head,int data){ Node temp=(Node)malloc(sizeof(node)); temp->data=data; temp->next=head->next; head->next=temp;//时间复杂度为O(1)#else//尾插法 Node p; p=head; while(p->next!=NULL)//时间复杂度为O(n)此处不能用p来进行判断,若p为尾结点的话也符合条件，但是进入循环后就不符合和会发生野指针的情况 { p=p->next; } p->next=temp; temp->next=NULL;}

3. 查找结点操作,由于单链表需要用指针进行移动,所以不能用二分法(假设存储的数据是有顺序的)进行查找

   123456789101112131415161718192021

   void findData(Node head,int data){ Node p; p=head; while(p!=NULL) { if(p->data==data) { printf("已找到数据"); break;//退出循环 } else { p=p->next; if(p==NULL) 大专栏  单链表的算法设计 { printf("未找到该数据"); } } }}

4. 删除结点

   12345678910111213141516171819

   void deleteData(Node head,int data){ Node p; p=head; while(p!=NULL) { Node temp; if(p->data==data) { temp=p->next; p->next=p->next->next; free(temp);//释放出删除的结点空间 } else { p=p->next; } }}

5. 删除单链表中的最大值结点

   12345678910111213141516171819

   void delMaxNode(Node head){ Node p=head->next; Node pre=head;//p和pre是同步运动的 Node maxp=p; Node maxpre=pre; which(p!=NULL) { if(maxp->data<p->data) { maxp=p; maxpre=pre;//最大值的前驱 } pre=p; p=p->next; } maxpre->next=maxp->next; free(maxp);}

6. 结点有序递增

   123456789101112131415161718

   void sort(Node head){ Node p,pre,q; p=head->next->next;//p指向L的第二个数据结点 head->next->next=NULL;//构造只含一个数据结点的有序表 while(p!=NULL) { q=p->next; pre=head; while(pre->next!=NULL&&pre->next->data<p->data) { pre=pre->next; } p->next=pre->next; pre->next=p; p=q; }}

解释如下图