数据结构学习笔记

数据结构学习笔记（一）

假期以来我都坚持每天看一点郝斌的数据结构视频。讲的很透彻，也很风趣。

前几天都是为讲数据结构而做准备，讲了一些结构体和指针，今天终于开始正式将数据结构。说实话，我今天才知道函数的用处。。

照着郝斌讲连续存储数组的算法演示，又自己写了一遍，发现有一个错误，左看右看都看不出哪错了，索性贴出了，，，有兴趣的朋友可以看看

百度求助，一位牛人看出错误来，谢谢了！重新贴出正确的代码

[cpp] view plaincopy

1. #include <stdio.h>  
2. #include <malloc.h>  
3. #include <stdlib.h>   //  包含exit  
4. int val,i,t;  
5. struct Arr  
6. {  
7.     int * pBase;    //储存的是数组第一个元素的地址  
8.     int len;    //数组所能容纳的最大元素个数  
9.     int cnt;    //当前数组有效个数  
10. };  
11. void init_arr(struct Arr * pArr,int length);    //初始化  
12. bool append_arr(struct Arr * pArr,int val);  
13. bool insert_arr(struct Arr * pArr,int pos,int val);     //pos的值从1开始  
14. bool delete_arr(struct Arr * pArr,int pos,int *pVal);  
15. int get();  
16. bool is_empty(struct Arr * pArr);  
17. bool is_full(struct Arr * pArr);  
18. void sort_arr(struct Arr * pArr);  
19. void show_arr(struct Arr * pArr);  
20. void inversion_arr(struct Arr * pArr);  //倒置  
21. int main()  
22. {  
23.     struct Arr arr;  
24.     init_arr(&arr,6);  
25.     show_arr(&arr);  
26.     append_arr(&arr,1);  
27.     append_arr(&arr,2);  
28.     append_arr(&arr,3);  
29.     append_arr(&arr,4);  
30.     delete_arr(&arr,1,&val);  
31.     return 0;  
32. }  
33. void init_arr(struct Arr * pArr,int length)  
34. {  
35.     pArr->pBase = (int *)malloc(sizeof(int) * length);  
36.     if (NULL == pArr->pBase)  
37.     {  
38.         printf("动态内存分配失败！\n");  
39.         exit(-1);   //终止整个程序  
40.     }  
41.     else  
42.     {  
43.         pArr->len = length;  
44.         pArr->cnt = 0;  
45.     }  
46.     return;  
47.   
48. }  
49. bool is_empty(struct Arr * pArr)  
50. {  
51.     if(0 == pArr->cnt)  
52.         return true;  
53.     else  
54.         return false;  
55. }  
56. bool is_full(struct Arr * pArr)  
57. {  
58.     if(pArr->cnt == pArr->len)  
59.         return true;  
60.     else  
61.         return false;  
62. }  
63. void show_arr(struct Arr * pArr)  
64. {  
65.     if( is_empty(pArr) )    //pArr本来就是地址  
66.     {  
67.         printf("数组为空\n");  
68.     }  
69.     else  
70.     {  
71.         for(int i=0;i<pArr->cnt;++i)  
72.             printf("%d   ",pArr->pBase[i]);  
73.         printf("\n");  
74.     }  
75. }  
76. bool append_arr(struct Arr * pArr,int val)  
77. {  
78.     if( is_full(pArr) )  
79.         return false;  
80.     else  
81.         pArr->pBase[pArr->cnt] = val;  
82.         (pArr->cnt)++;  
83.     return true;  
84. }  
85. bool insert_arr(struct Arr * pArr,int pos,int val)  
86. {  
87.     int i;  
88.     if(pos<1||pos>pArr->len)  
89.     for (i=pArr->cnt-1;i>=pos-1;--i)  
90.     {  
91.         pArr->pBase[i+1] = pArr->pBase[i];  
92.     }  
93.     pArr->pBase[pos-1] = val;  
94.     return true;  
95. }  
96. bool delete_arr(struct Arr * pArr,int pos,int *pVal)  
97. {  
98.     if ( is_empty(pArr) )  
99.         return false;  
100.     if (pos<1|| pos>pArr->cnt)  
101.         return false;  
102.     *pVal = pArr->pBase[pos-1];  
103.     for(i=pos; i<pArr->cnt;i++)  
104.     {  
105.         pArr->pBase[i-1] = pArr->pBase[i];  
106.     }  
107.     pArr->cnt--;  
108.     return true;  
109. }  
110. void inversion_arr(struct Arr * pArr)  
111. {  
112.     int i = 0;  
113.     int j = pArr->cnt-1;  
114.     int t;  
115.     while (i<j)  
116.     {  
117.         t = pArr->pBase[i];  
118.         pArr->pBase[i] = pArr->pBase[j];  
119.         pArr->pBase[j] = t;  
120.         i++;  
121.         j--;  
122.     }  
123.     return;  
124. }  
125. void sort_arr(struct Arr * pArr)  
126. {  
127.     int i,j;    //冒泡法  
128.     for(i=0;i<pArr->cnt;i++)  
129.     {  
130.         for(j=i+1;j<pArr->cnt;i++)  
131.         {  
132.             if(pArr->pBase[i] > pArr->pBase[j])  
133.             {  
134.                 t = pArr->pBase[i];  
135.                 pArr->pBase[i] = pArr->pBase[j];  
136.                 pArr->pBase[j] = t;  
137.             }  
138.         }  
139.     }  
140. }  
     

数据结构学习笔记（二）

今天看链表创建和链表遍历算法的演示，自己有照猫画虎写了一遍，遇到了1个错误，丢给M，还是他牛啊，火眼金睛一下就看出来了，贴出来，与大家分享

[cpp] view plaincopy

1. #include <stdio.h>  
2. #include <malloc.h>  
3. #include <stdlib.h>  
4. typedef struct Node  
5. {  
6.  int data; //数据域  
7.  struct Node * pNext; //指针域  
8. }NODE,* PNODE; //NODE等价于struct Node NODE,pNODE等价于struct Node *  
9.   
10. PNODE create_list(void);  
11. void traverse_list(PNODE pHead);  
12.   
13.   
14. void main()  
15. {  
16.  PNODE pHead = NULL; //等价于struct Node * pHead = NULL  
17.  pHead = create_list(); //创建一个非循环链表，并将该链表的头地址赋给pHead  
18.  traverse_list(pHead);  
19. }  
20. PNODE create_list(void)  
21. {  
22.  int len;  
23.  int i;  
24.  int val; //用来临时存放用户输入的结点的值  
25.  PNODE pHead = (PNODE)malloc(sizeof(NODE));  
26.  if (NULL == pHead)  
27.  {  
28.   printf("分配失败，程序终止！\n");  
29.   exit(-1);  
30.  }  
31.  PNODE pTail = pHead;  
32.  pTail->pNext = NULL;  
33.  printf("请输入您需要生成的链表节点个数：len:");  
34.  scanf("%d",&len);  
35.  for(i=0;i<len;len++)  
36.  {  
37.   printf("请输入第%d个链表节点的值",i+1);  
38.   scanf("%d",&val);  
39.   PNODE pNew = (PNODE)malloc(sizeof(NODE));  
40.   if (NULL == pHead)  
41.   {  
42.   printf("分配失败，程序终止！\n");  
43.   exit(-1);  
44.   }  
45.   pNew->data = val;  
46.   pTail->pNext = pNew;  
47.   pNew->pNext = NULL;  
48.   pTail = pNew;  
49.  }  
50.  return pHead;  
51. }  
52. void traverse_list(PNODE pHead)  
53. {  
54.  PNODE p = pHead->pNext;  
55.  while (NULL != p)  
56.  {  
57.   printf("%d    ",p->data);  
58.   p = p->pNext;  
59.   printf("\n");  
60.  }  
61.  return;  
62. } 
    

数据结构学习笔记（三）

郁闷！真心听不懂了！敲出代码也是错！百度知道无人解答！不管了，贴出来下午出去散散心！ [cpp] view plaincopy

1. #include <stdio.h>  
2. #include <malloc.h>  
3. #include <stdlib.h>  
4.   
5. typedef struct Node  
6. {  
7.     int data;   //数据域  
8.     struct Node * pNext;    //指针域  
9. }NODE,* PNODE;  //NODE等价于struct Node NODE,pNODE等价于struct Node *  
10.   
11. PNODE create_list(void);  
12. void traverse_list(PNODE pHead);  
13. bool is_empty(PNODE pHead);  
14. int length_list(PNODE);  
15. bool insert_list(PNODE,int pos,int val);    //在pHead所指的链表的第pos个节点的前面插入一个新的节点，该节点的值是val,并且pos的值从1开始  
16. bool delete_list(PNODE,int,int *);  
17. void sort_list(PNODE pHead);    //排序  
18. void main()  
19. {  
20.     PNODE pHead = NULL; //等价于struct Node * pHead = NULL  
21.     pHead = create_list();  //创建一个非循环链表，并将该链表的头地址赋给pHead  
22.     traverse_list(pHead);  
23. }  
24. PNODE create_list(void)  
25. {  
26.     int len;  
27.     int i;  
28.     int val;    //用来临时存放用户输入的结点的值  
29.     PNODE pHead = (PNODE)malloc(sizeof(NODE));  
30.     if (NULL == pHead)  
31.     {  
32.         printf("分配失败，程序终止！\n");  
33.         exit(-1);  
34.     }  
35.     PNODE pTail = pHead;  
36.     pTail->pNext = NULL;  
37.     printf("请输入您需要生成的链表节点个数：len:");  
38.     scanf("%d",&len);  
39.     for(i=0;i<len;len++)  
40.     {  
41.         printf("请输入第%d个链表节点的值",i+1);  
42.         scanf("%d",&val);  
43.         PNODE pNew = (PNODE)malloc(sizeof(NODE));  
44.         if (NULL == pHead)  
45.         {  
46.         printf("分配失败，程序终止！\n");  
47.         exit(-1);  
48.         }  
49.         pNew->data = val;  
50.         pTail->pNext = pNew;  
51.         pNew->pNext = NULL;  
52.         pTail = pNew;  
53.     }  
54.     return pHead;  
55. }  
56. void traverse_list(PNODE pHead)  
57. {  
58.     PNODE p = pHead->pNext;  
59.     while (NULL != p)  
60.     {  
61.         printf("%d    ",p->data);  
62.         p = p->pNext;  
63.         printf("\n");  
64.     }  
65.     return;  
66. }  
67. bool is_empty(PNODE pHead)  
68. {  
69.     if (NULL == pHead->pNext)  
70.         return true;  
71.     else  
72.         return false;  
73. }  
74. int length_list(PNODE)  
75. {  
76.     PNODE p= pHead->pNext;  
77.     int len = 0;  
78.     while (NULL !=p)  
79.     {  
80.         ++len;  
81.         p = p->pNext;  
82.     }  
83.     return len;  
84. }  
85. void sort_list(PNODE pHead)  
86. {  
87.     int i,j,t,len=0;  
88.     PNODE p,q;  
89.       
90.     for(i=0,p=pHead->pNext;i<len-1;++i,p=p->pNext)  
91.     {  
92.         for (j=i+1,q=p->pNext;j<len;++j,q=q->pNext)  
93.         {  
94.             if (p->data > q->data) //类似于数组中的：a[i]>a[j]  
95.             {  
96.                 t = p->data;//t = a[i];  
97.                 p->data = q->data;//a[i] = a[j];  
98.                 q->data = t;//a[j] = t;  
99.             }  
100.         }  
101.     }  
102.     return;  
103. }  
104. bool insert_list(PNODE,int pos,int val)  
105. {  
106.     int i = 0;  
107.     PNODE p = pHead;  
108.     while (NULL != p&& i<pos-1)  
109.     {  
110.         p = p->pNext;  
111.         ++i;  
112.     }  
113.     if (i>pos-1 ||NULL ==p)  
114.         return false;  
115.     PNODE pNew = (PNODE)malloc(sizeof(NODE));  
116.     if (NULL ==pNew)  
117.     {  
118.         printf("动态内存分配失败！\n");  
119.         exit(-1);  
120.     }  
121.     pNew->data = val;  
122.     PNODE q = p->pNext;  
123.     p->pNext = pNew;  
124.     pNew->pNext = q;  
125.     return true;  
126. }  
127. bool delete_list(PNODE,int pos,int * val)  
128. {  
129.     int i = 0;  
130.     PNODE p = pHead;  
131.     while (NULL != p&& i<pos-1)  
132.     {  
133.         p = p->pNext;  
134.         ++i;  
135.     }  
136.     if (i>pos-1 ||NULL ==p)  
137.         return false;  
138.     PNODE q = p->pNext;  
139.     *pVal = q->data;  
140.     //删除p节点后面的结点  
141.     PNODE q = p->pNext->pNext;  
142.     free(q);  
143.     q = NULL;  
144.     return true;  
145. } 
     

数据结构学习阶段总结（一）

数据结构

    狭义

                数据结构是专门研究数据存储问题

                数据的存储包含两个方面：个体的存储 + 个体关系的存储

    广义

                数据结构既包括数据存储也包括数据的操作

                对存储数据的操作就是算法

算法

         狭义

                 算法是和数据存储方式密切相关

         广义

                 算法和数据的存储方式无关

数据的存储结构

线性

连续存储【数组】

参照数据结构学习笔记（一）

优点 存取速度很快

缺点 插入删除元素很慢

          空间通常有限制

          必须知道数组长度

          需要大块连续内存

离散存储【链表】

参照数据结构学习笔记（三）

优点 空间没有限制

          插入删除元素很快

缺点  存取速度很慢

          线性结构的应用--栈

          线性结构的应用--队列

非线性

树，图

 

顺序存储结构的插入与删除

看了几个例子，心中有了些底子，把前面有些程序分割开，慢慢写出来。

插入算法思路：

1.如果插入不合理，抛出异常；

2.如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

3.从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；

4.将要插入元素填入位置i处；

5.表长加1.

[cpp] view plaincopy

1. //在L中第i个位置之前插入新元素e，L的长度加1  
2. int listinsert(Sqlist * L,int i,ElemType e)  
3. {  
4.     int k;  
5.     if (L->length == MAXSIZE)  
6.         return ERROR;  
7.     if (i<1 || i>L->length+1)  
8.         return ERROR;  
9.     if (i<=L->length)  
10.     {  
11.         for(k=L->length-1;k>=i;k--)   //后移一位  
12.             L->data[k+1] = L->data[k];  
13.     }  
14.     L->data[i-1] = e;    //插入  
15.     L->Length++;  
16.     return OK;  
17. }  

一样以来，简单明了。

删除算法思路不给出来了，和插入大同小异，给上代码

[cpp] view plaincopy

1. //删除L中第i个元素，并用e返回其值，L长度减1  
2. int listDelete(Sqlist * L,int i,ElemType e)  
3. {  
4.     int k;  
5.     if (L->length == 0)  
6.         return ERROR;  
7.     if (i<1 || i>L->length)  
8.         return ERROR;  
9.     *e =L->data[i-1];  
10.     if (i<=L->length)  
11.     {  
12.         for(k=i;k<=L->length;k++) //前移一位  
13.             L->data[k-1] = L->data[k];  
14.     }  
15.     L->length--；  
16.     return OK;  
17. } 
    

单链表的插入与删除

顺序结构的缺点还是蛮大的，现在来看看单链表的插入与删除。

单链表中，在C语言可以用结构体指针描述：

[cpp] view plaincopy

1. typedef struct Node  
2. {  
3.     ElemType data;  
4.     struct Node * next; //p->data,p->next->data  
5. }Node;  
6. typedef struct Node * LinkList  

 

有一点很重要

比如我随便画一个。。

 

千万别也成

p->next=s;s->netx=p->next;

正确的是

s->netx=p->next;p->next=s;

自己好好想想，不打了。记得是逆序就行了~

 

好，进入正题，单链表第i个数据插入节点的算法思路:

1.声明一节点p指向链表第一个结点，初始化j从1开始；

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；

3.若到链表末尾p为空，则说明第i个元素不存在；

4.否则查找成功，在系统中生成一个空节点s;

5.将数据元素e赋给s->data；

6.单链表插入标准语句s->next=p->next;p->next=s;

7.返回成功。

实现代码算法如下：

[cpp] view plaincopy

1. //在L中第i个位置之前插入新的数据元素e，L的长度加1  
2. int ListInsert(LinkList *L,int i,ElmeType e)  
3. {  
4.     int j;  
5.     LinkList p,s;  
6.     p = *L;  
7.     j = 1;  
8.     while(p && j<1)  
9.     {  
10.         p = p->next;  
11.         ++j;  
12.     }  
13.     if(!p || j>=1)  
14.         return ERROR;  
15.     s = (LinkList)malloc(sizeof(Node)); //生成新节点  
16.     s->data = e;  
17.     s->next = p->next;  
18.     p->next = s; //顺序绝对不变  
19.     return OK;  
20. }  

 

 

如何删除呢？其实只要q=p->next;p->next->q->next;

算法思路省略，直接给出代码：

[cpp] view plaincopy

1. //删除L第i个元素，并用e返回其值，L的长度减1  
2. int ListInsert(LinkList *L,int i,ElmeType e)  
3. {  
4.     int j;  
5.     LinkList p,s;  
6.     p = *L;  
7.     j = 1;  
8.     while(p && j<1)  
9.     {  
10.         p = p->next;  
11.         ++j;  
12.     }  
13.     if(!(p->next) || j>=1)  
14.         return ERROR;  
15.     q = p->next;  
16.     p->next = q->next;  
17.     *e = q->data;  
18.     free(q);    //释放内存  
19.     return OK;  
20. } 
    

单链表的整表创建--头插法，尾插法

创建单链表的过程是一个动态生成链表的过程。应依次建立各个结点，并逐个插入链表
给出头插法

[cpp] view plaincopy

1. //随机产生n个元素的值，建立代表头结点的单链线性表L（头插法）  
2. void CreateListHead(LinkList * L,int n)  
3. {  
4.     LinkList p;  
5.     int i;  
6.     srand(time(0)); //随机产生数  
7.     *L = (LinkList)malloc(sizeof(Node));  
8.     (*L)->next = NULL;   //先建立一个带头结点的单链表  
9.     for (i=0;i<n;i++)  
10.     {  
11.         p = (LinkList)malloc(sizeof(Node)); //生成新结点  
12.         p->data = rand()%100+1;  //随机生成1001以内的数字  
13.         p->next = (*L)->netx;  
14.         (*L)->next = p;  //插入到表头  
15.     }  
16. }  

 

尾插法：

[cpp] view plaincopy

1. //随机产生n个元素的值，建立代表头结点的单链线性表L（头插法）  
2. void CreateListTail(LinkList * L,int n)  
3. {     
4.     LinkList p,r;  
5.     int i;  
6.     srand(time(0)); //随机产生数  
7.     *L = (LinkList)malloc(sizeof(Node));  
8.     r = *L;  
9.     for (i=0;i<n;i++)  
10.     {  
11.         p = (LinkList)malloc(sizeof(Node)); //生成新结点  
12.         p->data = rand()%100+1;  //随机生成1001以内的数字  
13.         r->next = p; //将表尾终端结点指向新结点  
14.         r = p;  //将当前新结点定义为表尾终端结点  
15.     }  
16.     r->next = NULL;  //表示当前链表结束  
17. } 
    

单链表的整表删除

单链表的整表删除，先写一些算法思路

1.声明一节点p和q；

2.将第一个结点赋值给p；

3.循环：

           将下一结点赋值给q；

           释放p；

           将q赋值给p；

给出代码： [cpp] view plaincopy

1. bool clearList(LinkList * L)  
2. {  
3.     LinkList p,q;  
4.     p = (*L)->next;  
5.     while(p)  
6.     {  
7.         q = p->next;  
8.         free(p);  
9.         p = q;  
10.     }  
11.     (*L)->next = NULL;  
12.     return OK;  
13. } 
    

用数组组成的链表--静态链表

  C语言有指针，可以按照上次那个方法做一下，但JAVA，C#,Basic呢？怎么办？前辈们真是聪明，用数组描述指针。这个数组由两部分组成，一个位DATA域，一个位CUR指针域

线性表的静态链表存储结构

[cpp] view plaincopy

1. typedef struct   
2. {  
3.     ElemType data;  
4.     int cur;  /* 游标(Cursor) ，为0时表示无指向 */  
5. } Component,StaticLinkList[MAXSIZE];  

静态链表的插入

[cpp] view plaincopy

1. /*  在L中第i个元素之前插入新的数据元素e   */  
2. Status ListInsert(StaticLinkList L, int i, ElemType e)     
3. {    
4.     int j, k, l;     
5.     k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */  
6.     if (i < 1 || i > ListLength(L) + 1)     
7.         return ERROR;     
8.     j = Malloc_SSL(L);   /* 获得空闲分量的下标 */  
9.     if (j)     
10.     {     
11.         L[j].data = e;   /* 将数据赋值给此分量的data */  
12.         for(l = 1; l <= i - 1; l++)   /* 找到第i个元素之前的位置 */  
13.            k = L[k].cur;             
14.         L[j].cur = L[k].cur;    /* 把第i个元素之前的cur赋值给新元素的cur */  
15.         L[k].cur = j;           /* 把新元素的下标赋值给第i个元素之前元素的ur */  
16.         return OK;     
17.     }     
18.     return ERROR;     
19. }  

 

静态链表的元素删除

[cpp] view plaincopy

1. /*  删除在L中第i个数据元素   */  
2. Status ListDelete(StaticLinkList L, int i)     
3. {   
4.     int j, k;     
5.     if (i < 1 || i > ListLength(L))     
6.         return ERROR;     
7.     k = MAXSIZE - 1;     
8.     for (j = 1; j <= i - 1; j++)     
9.         k = L[k].cur;     
10.     j = L[k].cur;     
11.     L[k].cur = L[j].cur;     
12.     Free_SSL(L, j);     
13.     return OK;     
14. }