将线性表分为几个模块来学习：
1.单链表头插法建表
2.单链表尾插法建表
3.归并
4.划分
5.逆置
6.顺序表建表
7.顺序表删除
8.顺序表添加
9.最值问题
10.真题演练
-----------------------------------------------------------------------------------------------
1.单链表头插法建表：
1 /单链表头插法建表
2
3 /*
4 #inlclude<iostream>
5 using namespace std ;
6
7 void createLinkListH (Node *&head)
8 {
9 head = (*LNode)malloc(sizeof(LNode));
10 head->next = NULL ;
11 Node *p = NULL;
12 int n ;
13 cin >> n ;
14 for(int i = 0 ; i < N ; i++ )
15 {
16 p = (*LNode)malloc(sizeof(LNode));
17 p->next = NULL ;
18 cin >> p->data ;
19 p->next = head->next;
20 head->next = p ;
21 return 1 ;
22 }
23 }
24
25 */
26
27
28 /*
29
30 1.今天重点知识点是：malloc 函数
31 malloc 是动态内存分配函数，如果分配成功，则返回指向被分配内存的指针；
32 也就是说当分配成功的话，指针指向分配的那个函数，
33 链表中我们可以称要分配的那个节点，指针要指向它
34
35 2. malloc （）函数根据指令分配合适大小的空间，并且返回该空间的地址，
36 malloc 函数需要有一根参数，即需要分配的空间的大小，sizeof运算符会
37 计算出设计的结构体类型的空间大小。
38
39
40 */
View Code
2.单链表尾插法建表：
//单链表建表（尾插法）
/*
#include<iostream>
using namespace std ;
void createLinkListR(LNode *& head)
{
head = (*LNode)malloc(sizeof(LNode)); //创建头节点
head->next = NULL ; //头节点的下一个节点为空
LNode * r = head ; // r 指针指向的是已存在节点的最后一个指针，它始终指向链表的最后一个节点
LNode * p = NULL ; // p 指针指向的是创建新节点的位置
int n ; //定义要创建节点的个数
cin >> n ;
for(int i = 0 ; i < n ;i++ ) //为其依次赋值
{
p = (*LNode)malloc(sizeof(LNode)); // p指针为创建的新节点分配内存空间
p->next = NULL; // 令其下一个节点为空
cin >> p -> data; // 单链表分 数据域 和 指向前一个节点的地理位置 两个区域 ， 我们将节点数据域的值赋给该节点
// 插入链表的方式 ， （1）可省略 ，这里用链表插入的思维来实现链表的创建
p->next = r->next; //（1）
r->next = p ; // （2）
//将p位置付给r ，也就是说r实现了指针后移
r = p ;
}
}
*/
/*
p是不需要后移的，因为是单链表 ，不是顺序表 ， 只有创建完成 ，有那个连接就行 ，让 p->next = r->next ;
直接就能完成r 和 p 的关系 ， P 是不需要后移的， 也就不需要 ++ p ;
*/
View Code
3.归并：
1 //顺序表的归并
2
3 /*
4 void mergearry ( int a [] , int m , int b [] , int n , int c [] )
5 {
6 int i = 0 ;
7 int j = 0 ;
8 int k = 0 ;
9 while ( i < m && j < n )
10 {
11 if( a[i] < b[j])
12 {
13 c [k] = a [i] ;
14 k++ ;
15 i++ ;
16 }
17 else
18 {
19 c[k] = b [j] ;
20 k++ ;
21 j++ ;
22 }
23 }
24 while( i < m )
25 {
26 c [k] = a [i] ;
27 k++ ;
28 i++ ;
29 }
30 while( j < n )
31 {
32 c[k] = b [j] ;
33 k++ ;
34 j++ ;
35 }
36 }
37
38 */
39
40 //链表归并 （尾插）
41
42 /*
43 void merge (LNode *A , LNode *B ,LNode *&C ,int m ,int n ) //m和n代表着 两个链表的长度
44 {
45 LNode *p = A->next;
46 LNode *q = B->next;
47 LNode *r //指向目标链表的末尾结点,(每次插入之前的)
48 C = A ;
49 C->next = NULL ;
50 free(B);
51 r = C ;
52 while(p != NULL && q != NULL)
53 {
54 if(p->data < q->data)
55 {
56 r ->next = p ;
57 p = p->next ;
58 r = r->next ;
59 }
60 else
61 {
62 r ->next = q ;
63 q = q->next ;
64 r = r->next ;
65 }
66 }
67 if(q != NULL)
68 r->next = q ;
69 if(p != NULL)
70 r->next = p ;
71 }
72 */
73
74 //链表归并 （头插）
75
76 /*
77 void mergeR (LNode *A , LNode *B ,LNode*&C )
78 {
79 LNode *p = A -> next ;
80 LNode *q = B -> next ;
81 LNode *s // 存取要插入的最小值的临时寄存区域。并用该指针去插入到新的链表中，（头插）。
82 C = A ;
83 C -> next = NULL ;
84 free(B);
85 while(p ！= NULL && q != NULL )
86 {
87 if(p->data < q->data)
88 {
89 s = p ;
90 p = p -> next ;
91 s -> next = C -> next ;
92 C -> next = s;
93 }
94 else
95 {
96 s = q ;
97 q = q -> next ;
98 s -> next = C -> next ;
99 C -> next = s;
100 }
101 }
102 while(p != NULL )
103 {
104 s = p ;
105 p = p -> next ;
106 s -> next = C -> next ;
107 C -> next = s;
108
109 }
110 while(q != NULL )
111 {
112 s = q ;
113 q = q -> next ;
114 s -> next = C -> next ;
115 C -> next = s;
116 }
117
118 }
119 */
View Code
4.划分：
1 void partition ( int arr [] , int n )
2 {
3 int temp ; //定义一个变量
4 int i = 0 , j = n-1 ; //数组（顺序表）首段和尾端的定义（相当于数组）
5 temp = arr [i]; //变量存入数组第一个变量
6 while( i < j )
7 {
8 while( i < j && arr [ j ] > temp ) --j ;
9 if ( i < j )
10 {
11 arr [ j ] = arr [ i ];
12 ++ i ;
13 }
14 while( i < j && arr [ i ] < temp ) ++i ;
15 if( i < j )
16 {
17 arr[ i ] = arr [ j ];
18 -- j ;
19 }
20 }
21 arr [ i ] = temp ;
22 }
View Code
5.逆置：
1 // 1. 顺序表逆置问题
2
3 /*
4 int temp ;
5 int a [maxSize] = {1,2,3,4,5,7,6} ;
6
7 for(int i = left , j = right ; i < j ; i++ ,j--)
8 {
9 temp = a[i];
10 a[i] = a[j];
11 a[j] = temp;
12 }
13 */
14
15 // 2.链表逆置问题
16
17 /*
18 //t指向的是p->next ;
19 //p指向的最开始的节点；
20 //q始终指向的是最初的末尾节点
21 //p 和 q 是定向的指针 ， 而 t 是动态的指针 ； LNode * p ; LNode * q ； LNode *&t ;
22 while（p->next != q ）
23 {
24 t = p->next ;
25 p->next = t->next;
26 t->next = q->next;
27 q->next = t ;
28 }
29 */
30
31 //3.真题演练2
32
33 /*
34
35 题目：
36 1）将一长度为n的数组的前端k(k<n)个元素逆序后移动到数组后端，
37 要求原数组中的数据不丢失。
38 2）将一长度为n的数组的前端k(k<n)个元素保持原序移动到数组后端，
39 要求原数组中的数据不丢失。
40 3）将数组中的元素（X0 , X1, ...Xn-1），经过移动后变为：
41 （Xp,Xp+1,...Xn-1,X0,X1,...Xp-1）,即循环左移p(0<p<n)个位置。
42
43 */
44
45
46 /*
47 1）
48 #include<iostream>
49 using namespace std ;
50
51 void reverse (int a [] , int left , int right , int k)
52 {
53 int temp ;
54 for(int i = left , j = right ; i < j && i < left + k ; i++ , j-- )
55 {
56 temp = a [ i ];
57 a [ i ] = a [ j ];
58 a [ j ] = temp ;
59 }
60 }
61 */
62
63
64 /*
65 2）
66 自己的思路
67 void reverse (int k , int a [] , int left , int right ,int length)
68 {
69 for( int i = 0 ; i < k ; i++ )
70 for(int j = 0 ; j < length + 1 ; j++ )
71 {
72 a[length - i ] = a[i] ;
73 a[j] = a[j+1];
74 }
75 }
76 */
77
78 /*率辉
79
80 //两次逆值使其顺序变为正序，
81 1.第一次逆值是将前k个元素进行逆值
82 2.第二次就是第一题的原理，正好得出相反的结果
83
84 void movetoEnd (int a [] , int n , int k )
85 {
86 reverse(a , 0 , k-1 , k );
87 reverse(a , 0 , n-1 , k );
88 }
89
90 */
91
92 /*
93 3）
94 通过三次的逆置实现
95 1. 0 ~ p-1
96 2. p ~ n
97 3. 0 ~ n
98
99 void moveP (int a[] , int n , int p )
100 {
101 reverse(a,0,p-1,p);
102 reverse(a,p,n-1,n-p);
103 reverse(a,0,n-1,n);
104 }
105
106 */
View Code
6.顺序表建表：
1 //顺序表（建表）
2
3 /*
4 #include<iostream>
5 using namespace std ;
6
7 //定义数组和长度
8
9 int length ;
10 int A[maxSize] ;
11
12 //创建函数 ， 两个元素都是变量
13 int creatList(int A [] , int & length )
14 {
15 //输入你想要创建的表的长度
16 cin>>length ;
17 //判断不合理的条件
18 if(length < 0 || length >maxSize)
19 return 0 ;
20 //如何合理，递归依次赋值
21 for(int i = 0 ; i < length ; i++)
22 cin>>A[i];
23 return 1 ;
24 }
25 */
View Code
7.顺序表删除：
1 //顺序表（删除）
2
3 /*
4 #include<iostream>
5 using namespace std ;
6
7 int deleteElem (int sqLiset[] , int &length , int p , int &e) //数组 ， 长度 ，删除的下表 ， 存放删除某元素的变量
8 {
9 if(p < 0 || p > length-1 ) //先进行非法的判断，当插入的位置非法时候，返回值0，结束程序
10 return 0 ;
11 e = sqLiset[p] ; //存放删除的元素
12 for(int i = p ; i < length-1 ;i++) //逐步赋值 元素前移
13 sqLiset[i] = sqLiset[i+1];
14 --length ; //个数刷新
15 return 1 ;
16
17 }
18 */
View Code
8.顺序表添加：
1 //顺序表（插入）
2
3 /*
4 #include<iostream>
5 using namespace std;
6
7 int sqList [maxSize] = {1,2,3,4,5,....,n}; //定义一个整形的一维数组
8 int length = n ; //定义数组元素的个数
9 int insertELem(int sqLiset [] , int &length , int p , int e ) // 数组，长度，p是要插入的位置 ，e是要插入的元素
10 {
11 if( p < 0 || p > length || length == maxSize) //先进行非法的判断，当插入的位置非法时候，返回值0，结束程序
12 return 0 ;
13 for(int i = length-1 ; i>=p ; --i) //顺序表插入是插入元素后面的元素逐个后移，（* 从后往前向后移动 [为了防止元素覆盖的问题发生]）
14 sqLiset[i+1] = sqLiset[i]; //逐步后移
15 sqLiset[p] = e ; //插入，赋值
16 ++length ; //数组的元素个数+1 ；
17 return 1 ;
18 }
19 */
20
View Code
9.最值问题：
1 // 线性表中的最小值
2
3 /*
4 int min = a[0]; //定义线性表中第一个节点的元素是最小值
5 int minIdx = 0 ; //定义下标，定位最小值数组元素的小标
6 for( int i = 0 ; i < n ; i++ )
7 {
8 if(min > a[i])
9 {
10 min = a[i];
11 minIdx = i ;
12 }
13
14 }
15 */
16
17 //（同理）
18 //线性表中的最大值
19 /*
20 int max = a[0];
21 int maxIdx = 0 ;
22 for(int i = 0 ; i < n ; i++ )
23 {
24 if(max < a[i])
25 {
26 max = a[i];
27 minIdx = i ;
28 }
29 }
30 */
31
32 //链表的最大值
33
34 /*
35 LNode *p , *q ;
36 int max = head->next->data ;
37 q = p = head->next;
38 while( p != NULL )
39 {
40 if(max < p->data)
41 {
42 max = p -> data ;
43 q = p ;
44
45 }
46 p = p->next ;
47 }
48 */
49
50 //链表的最大值
51
52 /*
53 LNode *p , *q ;
54 int min = head->next->data;
55 p = q = head->next ;
56 while(p != NULL )
57 {
58 if(min > p->data)
59 {
60 min = p -> data ;
61 q = p ;
62 }
63 p = p -> next ;
64 }
65
66 */
67
68 //真题演练
69
70 /*
71 一双链表非空，由head指针指出，节点结构为（llink , data ,rlink）,请设计一个
72 将结点数据域 data 值最大的那个结点（最大值结点只有一个）移动到链表最前边的算法，
73 要求不得申请新的结点空间。
74 */
75
76 /*
77
78 typedef struct DLNode
79 {
80 int data ;
81 struct DLNode *llink ;
82 struct DLNode *rlink ;
83 }DLNode;
84
85 void maxFirst (DLNode *head)
86 {
87 DLNode *p = head -> rlink , *q = * p ;
88 max = p -> data ;
89 //找最值
90 while(p != NULL)
91 {
92 if(max < p->data)
93 {
94 max = p -> data ;
95 q = p ;
96 }
97 p = p -> rlink ;
98 }
99 //删除
100 //定位p的的左右结点 ，让他俩建立联系。从而使 p 断开链表的连接 ,间接的删除.
101 DLNode *l = q -> llink ;
102 DLNode *r = q -> rlink ;
103 l -> rlink = r ;
104 if(r != NULL)
105 {
106 r -> llink = l ;
107 }
108 //插入
109 q -> llink = head ;
110 q -> rlink = head -> next ;
111 head -> rlink = q ;
112 head -> rlink -> llink = q ;
113 }
114
115
116 */
View Code
10.真题演练：
1 /*
2 题目：
3 键盘输入n个英文字母，输入格式为 n , c1 , c2 , ....... , cn ,其中n表示字母的个数。
4 请编程以这些输入数据建立一根单链表，并要求将字母不重复的存入链表。
5 */
6
7 /*
8 解析：
9 输入一个单词，扫描其在链表中是否出现，如果出现，就什么都不做；
10 否则，根据这个单词构造节点插入链表中。
11 */
12
13 /*
14 #include<iostream>
15 using namespace std ;
16
17 void createLinkNoSameElem (LNode *&head)
18 {
19 head = (LNode*)malloc(sizeof(LNode));
20 head->next = NULL ;
21 int n ; //存储个数
22 char ch; //存储字符数据的
23 Node * p;
24 cin >> n ;
25 for(int i =0 ; i < n ; i++ )
26 {
27 cin >> ch ;
28 p = head -> next ;
29 while(p == NULL)
30 {
31 P = (LNode*)malloc(sizeof(LNode));
32 p-> data = ch ;
33 p -> next = head -> next ;
34 head -> next = p ;
35 }
36 while(p != NULL)
37 {
38 if( p -> data == ch )
39 break ;
40 p = p -> next ;
41 }
42 }
43 }
44
45 */
View Code