数据结构学习笔记

数据结构学习笔记（一）

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

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

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

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

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>//包含exit
intval,i,t;
structArr
{
int*pBase;//储存的是数组第一个元素的地址
intlen;//数组所能容纳的最大元素个数
intcnt;//当前数组有效个数
};
voidinit_arr(structArr*pArr,intlength);//初始化
boolappend_arr(structArr*pArr,intval);
boolinsert_arr(structArr*pArr,intpos,intval);//pos的值从1开始
booldelete_arr(structArr*pArr,intpos,int*pVal);
intget();
boolis_empty(structArr*pArr);
boolis_full(structArr*pArr);
voidsort_arr(structArr*pArr);
voidshow_arr(structArr*pArr);
voidinversion_arr(structArr*pArr);//倒置
intmain()
{
structArrarr;
init_arr(&arr,6);
show_arr(&arr);
append_arr(&arr,1);
append_arr(&arr,2);
append_arr(&arr,3);
append_arr(&arr,4);
delete_arr(&arr,1,&val);
return0;
}
voidinit_arr(structArr*pArr,intlength)
{
pArr->pBase=(int*)malloc(sizeof(int)*length);
if(NULL==pArr->pBase)
{
printf("动态内存分配失败！\n");
exit(-1);//终止整个程序
}
else
{
pArr->len=length;
pArr->cnt=0;
}
return;

}
boolis_empty(structArr*pArr)
{
if(0==pArr->cnt)
returntrue;
else
returnfalse;
}
boolis_full(structArr*pArr)
{
if(pArr->cnt==pArr->len)
returntrue;
else
returnfalse;
}
voidshow_arr(structArr*pArr)
{
if(is_empty(pArr))//pArr本来就是地址
{
printf("数组为空\n");
}
else
{
for(inti=0;i<pArr->cnt;++i)
printf("%d",pArr->pBase[i]);
printf("\n");
}
}
boolappend_arr(structArr*pArr,intval)
{
if(is_full(pArr))
returnfalse;
else
pArr->pBase[pArr->cnt]=val;
(pArr->cnt)++;
returntrue;
}
boolinsert_arr(structArr*pArr,intpos,intval)
{
inti;
if(pos<1||pos>pArr->len)
for(i=pArr->cnt-1;i>=pos-1;--i)
{
pArr->pBase[i+1]=pArr->pBase[i];
}
pArr->pBase[pos-1]=val;
returntrue;
}
booldelete_arr(structArr*pArr,intpos,int*pVal)
{
if(is_empty(pArr))
returnfalse;
if(pos<1||pos>pArr->cnt)
returnfalse;
*pVal=pArr->pBase[pos-1];
for(i=pos;i<pArr->cnt;i++)
{
pArr->pBase[i-1]=pArr->pBase[i];
}
pArr->cnt--;
returntrue;
}
voidinversion_arr(structArr*pArr)
{
inti=0;
intj=pArr->cnt-1;
intt;
while(i<j)
{
t=pArr->pBase[i];
pArr->pBase[i]=pArr->pBase[j];
pArr->pBase[j]=t;
i++;
j--;
}
return;
}
voidsort_arr(structArr*pArr)
{
inti,j;//冒泡法
for(i=0;i<pArr->cnt;i++)
{
for(j=i+1;j<pArr->cnt;i++)
{
if(pArr->pBase[i]>pArr->pBase[j])
{
t=pArr->pBase[i];
pArr->pBase[i]=pArr->pBase[j];
pArr->pBase[j]=t;
}
}
}
}

数据结构学习笔记（二）

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

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedefstructNode
{
intdata;//数据域
structNode*pNext;//指针域
}NODE,*PNODE;//NODE等价于structNodeNODE,pNODE等价于structNode*

PNODEcreate_list(void);
voidtraverse_list(PNODEpHead);


voidmain()
{
PNODEpHead=NULL;//等价于structNode*pHead=NULL
pHead=create_list();//创建一个非循环链表，并将该链表的头地址赋给pHead
traverse_list(pHead);
}
PNODEcreate_list(void)
{
intlen;
inti;
intval;//用来临时存放用户输入的结点的值
PNODEpHead=(PNODE)malloc(sizeof(NODE));
if(NULL==pHead)
{
printf("分配失败，程序终止！\n");
exit(-1);
}
PNODEpTail=pHead;
pTail->pNext=NULL;
printf("请输入您需要生成的链表节点个数：len:");
scanf("%d",&len);
for(i=0;i<len;len++)
{
printf("请输入第%d个链表节点的值",i+1);
scanf("%d",&val);
PNODEpNew=(PNODE)malloc(sizeof(NODE));
if(NULL==pHead)
{
printf("分配失败，程序终止！\n");
exit(-1);
}
pNew->data=val;
pTail->pNext=pNew;
pNew->pNext=NULL;
pTail=pNew;
}
returnpHead;
}
voidtraverse_list(PNODEpHead)
{
PNODEp=pHead->pNext;
while(NULL!=p)
{
printf("%d",p->data);
p=p->pNext;
printf("\n");
}
return;
}

数据结构学习笔记（三）

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

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedefstructNode
{
intdata;//数据域
structNode*pNext;//指针域
}NODE,*PNODE;//NODE等价于structNodeNODE,pNODE等价于structNode*

PNODEcreate_list(void);
voidtraverse_list(PNODEpHead);
boolis_empty(PNODEpHead);
intlength_list(PNODE);
boolinsert_list(PNODE,intpos,intval);//在pHead所指的链表的第pos个节点的前面插入一个新的节点，该节点的值是val,并且pos的值从1开始
booldelete_list(PNODE,int,int*);
voidsort_list(PNODEpHead);//排序
voidmain()
{
PNODEpHead=NULL;//等价于structNode*pHead=NULL
pHead=create_list();//创建一个非循环链表，并将该链表的头地址赋给pHead
traverse_list(pHead);
}
PNODEcreate_list(void)
{
intlen;
inti;
intval;//用来临时存放用户输入的结点的值
PNODEpHead=(PNODE)malloc(sizeof(NODE));
if(NULL==pHead)
{
printf("分配失败，程序终止！\n");
exit(-1);
}
PNODEpTail=pHead;
pTail->pNext=NULL;
printf("请输入您需要生成的链表节点个数：len:");
scanf("%d",&len);
for(i=0;i<len;len++)
{
printf("请输入第%d个链表节点的值",i+1);
scanf("%d",&val);
PNODEpNew=(PNODE)malloc(sizeof(NODE));
if(NULL==pHead)
{
printf("分配失败，程序终止！\n");
exit(-1);
}
pNew->data=val;
pTail->pNext=pNew;
pNew->pNext=NULL;
pTail=pNew;
}
returnpHead;
}
voidtraverse_list(PNODEpHead)
{
PNODEp=pHead->pNext;
while(NULL!=p)
{
printf("%d",p->data);
p=p->pNext;
printf("\n");
}
return;
}
boolis_empty(PNODEpHead)
{
if(NULL==pHead->pNext)
returntrue;
else
returnfalse;
}
intlength_list(PNODE)
{
PNODEp=pHead->pNext;
intlen=0;
while(NULL!=p)
{
++len;
p=p->pNext;
}
returnlen;
}
voidsort_list(PNODEpHead)
{
inti,j,t,len=0;
PNODEp,q;

for(i=0,p=pHead->pNext;i<len-1;++i,p=p->pNext)
{
for(j=i+1,q=p->pNext;j<len;++j,q=q->pNext)
{
if(p->data>q->data)//类似于数组中的：a[i]>a[j]
{
t=p->data;//t=a[i];
p->data=q->data;//a[i]=a[j];
q->data=t;//a[j]=t;
}
}
}
return;
}
boolinsert_list(PNODE,intpos,intval)
{
inti=0;
PNODEp=pHead;
while(NULL!=p&&i<pos-1)
{
p=p->pNext;
++i;
}
if(i>pos-1||NULL==p)
returnfalse;
PNODEpNew=(PNODE)malloc(sizeof(NODE));
if(NULL==pNew)
{
printf("动态内存分配失败！\n");
exit(-1);
}
pNew->data=val;
PNODEq=p->pNext;
p->pNext=pNew;
pNew->pNext=q;
returntrue;
}
booldelete_list(PNODE,intpos,int*val)
{
inti=0;
PNODEp=pHead;
while(NULL!=p&&i<pos-1)
{
p=p->pNext;
++i;
}
if(i>pos-1||NULL==p)
returnfalse;
PNODEq=p->pNext;
*pVal=q->data;
//删除p节点后面的结点
PNODEq=p->pNext->pNext;
free(q);
q=NULL;
returntrue;
}

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

数据结构

狭义

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

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

广义

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

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

算法

狭义

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

广义

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

数据的存储结构

线性

连续存储【数组】

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

优点 存取速度很快

缺点 插入删除元素很慢

空间通常有限制

必须知道数组长度

需要大块连续内存

离散存储【链表】

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

优点 空间没有限制

插入删除元素很快

缺点 存取速度很慢

线性结构的应用--栈

线性结构的应用--队列

非线性

树，图

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

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

插入算法思路：

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

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

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

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

5.表长加1.

//在L中第i个位置之前插入新元素e，L的长度加1
intlistinsert(Sqlist*L,inti,ElemTypee)
{
intk;
if(L->length==MAXSIZE)
returnERROR;
if(i<1||i>L->length+1)
returnERROR;
if(i<=L->length)
{
for(k=L->length-1;k>=i;k--)//后移一位
L->data[k+1]=L->data[k];
}
L->data[i-1]=e;//插入
L->Length++;
returnOK;
}

一样以来，简单明了。

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

//删除L中第i个元素，并用e返回其值，L长度减1
intlistDelete(Sqlist*L,inti,ElemTypee)
{
intk;
if(L->length==0)
returnERROR;
if(i<1||i>L->length)
returnERROR;
*e=L->data[i-1];
if(i<=L->length)
{
for(k=i;k<=L->length;k++)//前移一位
L->data[k-1]=L->data[k];
}
L->length--；
returnOK;
}

单链表的插入与删除

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

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

typedefstructNode
{
ElemTypedata;
structNode*next;//p->data,p->next->data
}Node;
typedefstructNode*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.返回成功。

实现代码算法如下：

//在L中第i个位置之前插入新的数据元素e，L的长度加1
intListInsert(LinkList*L,inti,ElmeTypee)
{
intj;
LinkListp,s;
p=*L;
j=1;
while(p&&j<1)
{
p=p->next;
++j;
}
if(!p||j>=1)
returnERROR;
s=(LinkList)malloc(sizeof(Node));//生成新节点
s->data=e;
s->next=p->next;
p->next=s;//顺序绝对不变
returnOK;
}

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

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

//删除L第i个元素，并用e返回其值，L的长度减1
intListInsert(LinkList*L,inti,ElmeTypee)
{
intj;
LinkListp,s;
p=*L;
j=1;
while(p&&j<1)
{
p=p->next;
++j;
}
if(!(p->next)||j>=1)
returnERROR;
q=p->next;
p->next=q->next;
*e=q->data;
free(q);//释放内存
returnOK;
}

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

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

//随机产生n个元素的值，建立代表头结点的单链线性表L（头插法）
voidCreateListHead(LinkList*L,intn)
{
LinkListp;
inti;
srand(time(0));//随机产生数
*L=(LinkList)malloc(sizeof(Node));
(*L)->next=NULL;//先建立一个带头结点的单链表
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(Node));//生成新结点
p->data=rand()%100+1;//随机生成1001以内的数字
p->next=(*L)->netx;
(*L)->next=p;//插入到表头
}
}

尾插法：

//随机产生n个元素的值，建立代表头结点的单链线性表L（头插法）
voidCreateListTail(LinkList*L,intn)
{
LinkListp,r;
inti;
srand(time(0));//随机产生数
*L=(LinkList)malloc(sizeof(Node));
r=*L;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(Node));//生成新结点
p->data=rand()%100+1;//随机生成1001以内的数字
r->next=p;//将表尾终端结点指向新结点
r=p;//将当前新结点定义为表尾终端结点
}
r->next=NULL;//表示当前链表结束
}

单链表的整表删除

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

1.声明一节点p和q；

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

3.循环：

将下一结点赋值给q；

释放p；

将q赋值给p；

给出代码：

boolclearList(LinkList*L)
{
LinkListp,q;
p=(*L)->next;
while(p)
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;
returnOK;
}

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

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

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

typedefstruct
{
ElemTypedata;
intcur;/*游标(Cursor)，为0时表示无指向*/
}Component,StaticLinkList[MAXSIZE];

静态链表的插入

/*在L中第i个元素之前插入新的数据元素e*/
StatusListInsert(StaticLinkListL,inti,ElemTypee)
{
intj,k,l;
k=MAXSIZE-1;/*注意k首先是最后一个元素的下标*/
if(i<1||i>ListLength(L)+1)
returnERROR;
j=Malloc_SSL(L);/*获得空闲分量的下标*/
if(j)
{
L[j].data=e;/*将数据赋值给此分量的data*/
for(l=1;l<=i-1;l++)/*找到第i个元素之前的位置*/
k=L[k].cur;
L[j].cur=L[k].cur;/*把第i个元素之前的cur赋值给新元素的cur*/
L[k].cur=j;/*把新元素的下标赋值给第i个元素之前元素的ur*/
returnOK;
}
returnERROR;
}

静态链表的元素删除

/*删除在L中第i个数据元素*/
StatusListDelete(StaticLinkListL,inti)
{
intj,k;
if(i<1||i>ListLength(L))
returnERROR;
k=MAXSIZE-1;
for(j=1;j<=i-1;j++)
k=L[k].cur;
j=L[k].cur;
L[k].cur=L[j].cur;
Free_SSL(L,j);
returnOK;
}

数据结构

狭义

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

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

广义

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

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

算法

狭义

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

广义

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

数据的存储结构

线性

连续存储【数组】

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

优点 存取速度很快

缺点 插入删除元素很慢

空间通常有限制

必须知道数组长度

需要大块连续内存

离散存储【链表】

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

优点 空间没有限制

插入删除元素很快

缺点 存取速度很慢

线性结构的应用--栈

线性结构的应用--队列

非线性

树，图