数据结构读书笔记（一）（C语言）
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 第一章 & 关于数据结构
1.数据结构研究什么？（计算机加工的对象由数值&&&非数值）
& & 将现实生活中大量而复杂的问题（非数值问题）以特定的数据类型（逻辑结构）和特定的存储结构（物理结构）保存到主存储器中，以及在此基础上为实现某个功能（删除、排序）相对应的操作。
2.数据的逻辑结构：
3.存储结构（物理结构）：
&1）顺序存储结构（借助元素在存储器中的相对位置）
&2）链式存储结构（借助元素存储地址的指针）
4.抽象数据类型ADT：
ADT抽象数据类型名 &
& &数据对象：&数据对象的定义& &
& &数据关系：&数据对象之间关系的定义& &
& &基本操作：&基本操作的定义& &
5、时间复杂度：
取决定性作用语句的重复次数
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 第二章 & &线性表
1.线性结构的基本特征：
1）集合中必存在唯一的一个&第一个元素&；
2）集合中必存在唯一的一个&最后元素&；
3）除最后元素外，均有唯一的后继；
4）除第一元素之外，均有唯一的前驱；&
ADT List &
& 数据对象：D={ a1,a2, a3, ... an}; &
& 数据关系：R={&a1, a2&, &a2, a3&, &a3, a4& & &an-1, an&}； &&
& 基本操作： &
& InitList(&L); & & & & //操作结果：构造线性表； &
& DestroyList(&L)； & & //操作结果：销毁线性表； &
& ListEmpty(L)； & & & &//操作结果：若L为空表，则返回TRUE,否则FALSE; &
& ListLength(L)； & & & //操作结果：返回L中元素个数； & & & & & &
& PriorElem(L,cur_e,&pre_e)//操作结果：cur_e是L的元素，但不是第一个 &
& & & & & & & & & & & & & &//则用pre_e返回它的前驱。若操作失败,pre_e无定义 &
& NextElem(L,cur_e,&next_e)//操作结果：cur_e是L的元素，但不是最后一个， &
& & & & & & & & & & & & & &//则用next_e返回它的后继。若操作失败，next_e无定义 & &
& GetElem(L,i,&e) // &1&= i &=LengthList(L) 操作结果：用e返回L中第i个元素的值。 &
& LocateElem(L,e,compare())//compare()是元素判定函数。返回L中第一个与e满足compare()的元素位序。 &
& & & & & & & & & & & & & &//若这样的元素不存在，则返回值为0。 &
& ListTraverse(L,visit( )) //依次对L的每个元素调用函数visit( ).一旦visit( )失败，则操作失败 &
& ClearList(&L) & & & & //操作结果将L重置为空表。 &
& PutElem(L,i,&e) & &//1&=i&=LengthList(L) &结果：L中第i个元素赋值为e &
& ListInsert(&L，i,e) //1&=i &=LengthList(L) +1 &结果：在L的第i个元素之前插入新的元素e,L的长度增1 &
& ListDelete(&L，i,&e)//1&=i &=LengthList(L) 结果：删除L的第i个元素，并用e返回其值，,L的长度减1 &
}ADT List &
3.顺序实现
&1）存储结构：
#define LIST_INIT_SIZE & 10 &
#define INCREAMENT & 2 &
struct SqList &
& & ElemType * &
&2）基本操作
void InitList(SqList & L ) &
& & L.elem & = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType) ); &
& & L.length = 0; &
& & L.listsize = LIST_INIT_SIZE; &
void DestroyList(SqList & L) &
& & free(L.elem); &
& & L.elem = NULL; &
& & L.length = 0; &
& & L.listsize = 0; &
void ClearList( SqList & L) &
& & L.length = 0; &
Status ListEmpty( SqList L) &
& & if( L.length != 0 ) &
& & & & return FALSE; &
& & else &
& & & & return TRUE; &
int ListLength(SqList L) &
& & return L. &
Status GetElem(SqList L, int i , ElemType & e) &
& & if( i & 1 || i & L.length ) &
& & & & return ERROR; &
& & e = *(L.elem + i - 1); &
& & return OK; &
int LocateElem(SqList L,ElemType e, Status(*compare)(ElemType , ElemType)) &
& & ElemType * &
& & p = L. &
& & int i = 1; &
& & while(i & L.length && !(compare(e, *p))) &
& & & & i++; &
& & & & p++; &
& & if( i& L.length) &
& & else &
& & & & return 0; &
Status PriorElem(SqList L, ElemType cur_e, ElemType & pre_e) &
& & ElemType * &
& & p = L.elem + 1; & //p 和 i 之间进行合作 &
& & int i = 2; &
& & while(i & L.length && *p!=cur_e) &
& & & & i++; &
& & & & p++; &
& & if( i& L.length) &
& & & & pre_e = *(--p); &
& & & & return OK; &
& & else &
& & & & return INFEASIBLE; &
Status NextElem(SqList L,ElemType cur_e,ElemType &next_e) &
&{ // 初始条件：顺序线性表L已存在 &
& &// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， &
& &// & & & & & 否则操作失败，next_e无定义 &
& &int i=1; &
& &ElemType *p=L. &
& &while(i&L.length&&*p!=cur_e) &
& & &i++; &
& & &p++; &
& &if(i==L.length) &
& & &return INFEASIBLE; // 操作失败 &
& & &next_e=*++p; &
& & &return OK; &
Status ListInsert(SqList & L, int i , ElemType e) &
& & if(i & 1 || i & L.length + 1) &
& & & & return ERROR; &
& & ElemType * &
& & if(L.length &= L.listsize) &
& & & newbase = (ElemType *)realloc(L.elem,( L.listsize + INCREAMENT) * sizeof(ElemType)); &
& & & L.listsize = L.listsize + INCREAMENT; &&
& & & if(!newbase) &
& & & & exit(OVERFLOW); &
& & & L.elem = &
& & ElemType * p,*q; &
& & p = L.elem + L.length -1; &
& & q = L.elem + i -1; &
& & for(p = L.elem + L.length -1; p &= &--p) &
& & & & *(p + 1) = * &&
& & } & &&
& & *q = &
& & L.length = L.length + 1; &
& & return OK; &
&Status ListDelete(SqList &L,int i,ElemType &e) // 算法2.5 &
&{ // 初始条件：顺序线性表L已存在，1&i&ListLength(L) &
& &// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 &
& &ElemType *p,*q; &
& &if(i&1||i&L.length) // i值不合法 &
& & &return ERROR; &
& &p=L.elem+i-1; // p为被删除元素的位置 &
& &e=*p; // 被删除元素的值赋给e &
& &q=L.elem+L.length-1; // 表尾元素的位置 &
& &for(++p;p&=q;++p) // 被删除元素之后的元素左移 &
& & &*(p-1)=*p; &
& &L.length--; // 表长减1 &
& &return OK; &
&void ListTraverse(SqList L,void(*vi)(ElemType & )) &
&{ // 初始条件：顺序线性表L已存在 &
& &// 操作结果：依次对L的每个数据元素调用函数vi() &
& &// & & & & & vi()的形参加'&'，表明可通过调用vi()改变元素的值 &
& &ElemType *p; &
& &for(i=1;i&=L.i++) &
& & &vi(*p++); &
& &printf(&\n&); &
4.链式实现
1）存储结构：
struct LNode &
& & ElemT &
& & LNode * &
typedef LNode * LinkL &
2）基本操作：
void InitList(LinkList &L) &
&{ // 操作结果：构造一个空的线性表L &
& &L=(LinkList)malloc(sizeof(LNode)); // 产生头结点，并使L指向此头结点 &
& &if(!L) // 存储分配失败 &
& & &exit(OVERFLOW); &
& &L-&next=NULL; // 指针域为空 &
&void DestroyList(LinkList &L) &
&{ // 初始条件：线性表L已存在。操作结果：销毁线性表L &
& &LinkL &
& &while(L) &
& & &q=L-& &
& & &free(L); &
& & &L=q; &
&void ClearList(LinkList L) // 不改变L &
&{ // 初始条件：线性表L已存在。操作结果：将L重置为空表 &
& &LinkList p,q; &
& &p=L-& // p指向第一个结点 &
& &while(p) // 没到表尾 &
& & &q=p-& &
& & &free(p); &
& & &p=q; &
& &L-&next=NULL; // 头结点指针域为空 &
&Status ListEmpty(LinkList L) &
&{ // 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE &
& &if(L-&next) // 非空 &
& & &return FALSE; &
& & &return TRUE; &
&int ListLength(LinkList L) &
&{ // 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 &
& &int i=0; &
& &LinkList p=L-& // p指向第一个结点 &
& &while(p) // 没到表尾 &
& & &i++; &
& & &p=p-& &
&Status GetElem(LinkList L,int i,ElemType &e) // 算法2.8 &
&{ // L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR &
& &int j=1; // j为计数器 &
& &LinkList p=L-& // p指向第一个结点 &
& &while(p&&j&i) // 顺指针向后查找，直到p指向第i个元素或p为空 &
& & &p=p-& &
& & &j++; &
& &if(!p||j&i) // 第i个元素不存在 &
& & &return ERROR; &
& &e=p-& // 取第i个元素 &
& &return OK; &
&int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) &
&{ // 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) &
& & /*操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。&
& & & & & & & 若这样的数据元素不存在，则返回值为0*/ &
& &int i=0; &
& &LinkList p=L-& &
& &while(p) &
& & &i++; &
& & &if(compare(p-&data,e)) // 找到这样的数据元素 &
& & &p=p-& &
& &return 0; &
Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) &
&{ // 初始条件: 线性表L已存在 &
& &/* 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，&
& & & & & & & 返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE*/ &
& &LinkList q,p=L-& // p指向第一个结点 &
& &while(p-&next) // p所指结点有后继 &
& & &q=p-& // q为p的后继 &
& & &if(q-&data==cur_e) &
& & & &pre_e=p-& &
& & & &return OK; &
& & &p=q; // p向后移 &
& &return INFEASIBLE; &
&Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) &
&{ // 初始条件：线性表L已存在 &
&/* & 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，&
& & & & & & & 返回OK;否则操作失败，next_e无定义，返回INFEASIBLE*/ &
& &LinkList p=L-& // p指向第一个结点 &
& &while(p-&next) // p所指结点有后继 &
& & &if(p-&data==cur_e) &
& & & &next_e=p-&next-& &
& & & &return OK; &
& & &p=p-& &
& &return INFEASIBLE; &
Status ListInsert(LinkList L,int i,ElemType e) // 算法2.9。不改变L &
&{ // 在带头结点的单链线性表L中第i个位置之前插入元素e &
& &int j=0; &
& &LinkList p=L,s; &
& &while(p&&j&i-1) // 寻找第i-1个结点 &
& & &p=p-& &
& & &j++; &
& &if(!p||j&i-1) // i小于1或者大于表长 &
& & &return ERROR; &
& &s=(LinkList)malloc(sizeof(LNode)); // 生成新结点 &
& &s-&data=e; // 插入L中 &
& &s-&next=p-& &
& &p-&next=s; &
& &return OK; &
&Status ListDelete(LinkList L,int i,ElemType &e) // 算法2.10。不改变L &
&{ // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 &
& &int j=0; &
& &LinkList p=L,q; &
& &while(p-&next&&j&i-1) // 寻找第i个结点，并令p指向其前驱 &
& & &p=p-& &
& & &j++; &
& &if(!p-&next||j&i-1) // 删除位置不合理 &
& & &return ERROR; &
& &q=p-& // 删除并释放结点 &
& &p-&next=q-& &
& &e=q-& &
& &free(q); &
& &return OK; &
&void ListTraverse(LinkList L,void(*vi)(ElemType)) &
& //vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同 &
&{ // 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi() &
& &LinkList p=L-& &
& &while(p) &
& & &vi(p-&data); &
& & &p=p-& &
& &printf(&\n&); &
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。顺序表中所有数据域值为X的结点替换成Y_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
文档贡献者贡献于
评价文档：
69页免费9页免费8页免费8页免费4页免费7页免费1页免费1页免费1页免费2页免费
喜欢此文档的还喜欢2页1下载券13页免费24页免费25页7下载券10页7下载券
顺序表中所有数据域值为X的结点替换成Y|
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
大小：5.98KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢数据结构常用算法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
暂无相关推荐文档
数据结构常用算法|顺​序​表​,​链​表​,​树​,​二​叉​树​,​递​归​以​及​查​找​排​序​的​常​用​算​法​。​初​学​必​备​。
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢include_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
18页免费3页1下载券8页免费1页免费4页免费5页免费4页免费1页免费3页1下载券1页免费
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢数据结构常用算法_中华文本库
第1页/共5页
文本预览：
顺序表的建立
Status InitList(SqList &L) { //构造一个空的顺序表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }
顺序表按照值查找位置
int LocateElem(SqList L, ElemType e) { //根据数据元素的值，返回它在线性表 L 中的位置 int i=0; while ((i<=L.length)&&(*(L.elem+i-1)!=e)) i++; if (i<=L.length) else return(-1); }
顺序表按照序号查找元素的值
Status GetElem(SqList L,int i,ElemType &e) { //根据数据元素在线性表 L 中的位置，返回它的值 if(iL.length) exit(ERROR); e=L.elem[i-1]; return OK; }
顺序表数据元素的插入
Status ListInsert(SqList &L,int i,ElemType e) { // 在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 int *q,*p; q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L. if(L.length>=L.listsize) ++L. return OK; }
顺序表数据元素的删除
Status ListDelete(SqList &L,int i,ElemType &e) { //删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 int *q,*p; if((iL.length)) return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; --L. return OK; }
顺序表数据元素输出单链表的操作
Status visit(SqList L) { //按序输出顺序表的各个元素值 for(i=1;i<=L.i++) printf("%2d"*(L.elem+i-1)); cout<< printf("L.elem=%u L.length=%d L.listsize=%d\u005cn"L.elem,L.length,L.listsize); return OK; }
单链表的建立
Status InitList(LinkList &L) {//构造一个空的单链表 L L=(LinkList)malloc(sizeof(LNode)); if (!L) exit(OVERFLOW); L->next=NULL; return OK; }
单链表的建立
void CreateList2(LinkList &L,int n) {//正位序输入 n 个元素的值， 建立带表头结构的单链线性表 LinkList p,q; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; q=L; printf("正位序，请输入%d 个数据:"n); for(i=1;i<=n;i++) { p=(LinkList)malloc(sizeof(LNode)); scanf("%d"&p->data); q->next=p; q=q-> } p->next=NULL; }
单链表的输出
Status visit(LinkList L) {//按序输出单链表的各个元素值 LinkList p=L->
while(p) { printf("%2d"p->data); p=p-> } printf("\u005cn"); return OK; }
单链表结点的插入
Status ListInsert(LinkList L,int i,ElemType e) { int j=0; LinkList p=L,s; while(p&&j j++; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p-> p->next=s; return OK; }
单链表结点的删除
Status ListDelete(LinkList L, int i,ElemType &e) { int j=0; LinkList p=L,q; while(p->next&&j ++j; }
if(!(p->next)||j>i-1) return 0; q=p-> p->next=q-> e=q-> free(q); return OK; }
单链表中按照结点值查找结点的位序
int LocateElem(LinkList L,ElemType e) {//返回 L 中第 1 个值为 e 的数据元素的位序， 若这样的数据元素不存在,则返回值为 0 int i=0;
第1页/共5页
寻找更多 ""}