第二章线性表

前言：线性表是最常用的一种数据结构。线性表是n个数据元素的有限序列。线性表有两种表示：顺序表示和链式表示。顺序表示是指以组连续的存储空间依次存储线性表的数据元素，如数组就是一个线性表。而链式表示的特带你是用一组任意的存储单元存储线性表的数据元素（也可以连续，也可以不联系）。在此，主要记录链式表的学习笔记。

线性链表

1.组成：指针域+数据域

2.分类：单链表（主要讲解单链表），双向链表，循环链表；

3.单链表的结构体类型定义：

typedef struct node {
    int info;
    node * next;
}HeadLink;

4.建立单链表（带头结点）的方法：头插法（逆序），尾插法（顺序）

 1 HeadLink *Creat(void)//头插发，逆序
 2 {
 3     char c;
 4     node *head,*p;
 5     head=(struct node *)malloc(sizeof(struct node));
 6     head->next=NULL;
 7     while((c=getchar())!='
')
 8     {
 9         p=(struct node *)malloc(sizeof(struct node));
10         p->info=c;
11         p->next=head->next;
12         head->next=p;
13     }
14     return head;
15 }
16 
17 HeadLink * Creat2(void)//尾插法
18 {
19     char c;
20     node *head, *last, *p;
21     head=(struct node *)malloc(sizeof(struct node));
22     head->next=NULL;
23     last=head->next;
24     while((c=getchar())!='
')
25     {
26         p=(struct node *)malloc(sizeof(struct node));
27         p->info=c;
28         p->next=NULL;
29         if(head->next==NULL)
30         {
31             head->next=p;
32             last=p;
33         }
34         else
35         {
36             last->next=p;
37             last=p;
38         }
39     }
40     return head;
41 }

View Code

//带有头结点的单链表的结点排序 HeadLink * Link_Sort(HeadLink * head) { HeadLink *p,*qnext,*rhead,*temp; p=head->next;//除去头节点 head->next=NULL; while(p)//执行N-1次 N为长度 { rhead=head; qnext=head->next; while(qnext&&qnext->info<=p->info)//查找插入位置 { rhead=qnext; qnext=qnext->next; } temp=p->next; p->next=rhead->next; rhead->next=p; p->next=temp; } return head; }

第二章 线性表

相关推荐