大学教程(零起点)数据结构--概论

教学目标：1. 理解数据结构的基本概念和重要性。

2. 掌握数据结构的逻辑结构和物理结构。

3. 了解数据结构的学习方法和应用领域。

教学重点：1. 数据结构的概念和重要性。

2. 逻辑结构和物理结构的基本概念。

教学难点：1. 数据结构的逻辑结构和物理结构的理解。

2. 数据结构的学习方法和应用领域的掌握。

教学准备：1. 教学课件。

2. 相关教材和参考资料。

3. 实例分析。

教学过程：一、导入1. 通过一个简单的例子（如学生信息管理系统），引出数据结构的概念。

2. 提问：在学生信息管理系统中，我们如何存储和操作学生信息？二、讲授新课1. 数据结构的概念- 数据结构是计算机存储、组织数据的方式。

- 数据结构是计算机科学中的重要基础，是解决复杂问题的有力工具。

2. 数据结构的重要性- 提高数据存储和处理的效率。

- 优化算法设计和分析。

- 促进软件开发和工程实践。

3. 逻辑结构和物理结构- 逻辑结构：描述数据之间的逻辑关系，如线性结构、非线性结构等。

- 物理结构：描述数据在计算机中的存储方式，如数组、链表、树等。

4. 数据结构的学习方法- 理论与实践相结合。

- 注重算法设计和分析。

- 学习经典数据结构及其应用。

5. 数据结构的应用领域- 软件开发。

- 数据库系统。

- 网络通信。

- 图像处理。

三、实例分析1. 以学生信息管理系统为例，分析数据结构的实际应用。

2. 引导学生思考：如何设计合适的数据结构来存储和操作学生信息？四、课堂小结1. 总结本章内容，强调数据结构的基本概念和重要性。

2. 鼓励学生课后继续学习，掌握数据结构的逻辑结构和物理结构。

五、作业布置1. 阅读教材相关内容，理解数据结构的逻辑结构和物理结构。

2. 完成课后习题，巩固所学知识。

教学反思：1. 本节课通过实例分析，使学生更加直观地理解数据结构的概念和应用。

2. 在教学过程中，注重启发式教学，引导学生主动思考。

3. 在课后作业布置中，注重理论与实践相结合，提高学生的动手能力。

数据结构自学总结--第一阶段线性结构一．数据结构概论1.1 时间复杂度：程序执行的次数T = O(n);1.2 空间复杂度:出现执行时所占用的内存空间；1.3数据结构的定义：狭义：是专门研究数据存储的问题数据的存储包含两方面：个体的存储+个体关系的存储广义：数据结构即包含数据的存储也包含数据的操作对存储数据的操作就是算法1.4算法的定义：是对存储数据的操作狭义的算法是与数据的存储方式密切相关广义的算法是与数据的存储方式无关泛型：利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的。

1.5 利用结构体定义自己的数据类型typedef struct Student{int sid;char name[100];char sex;}* PST,STU; //PST 等于struct student * ,STU代表了struct Student二．线性结构2.1连续存储（顺序表，数组）：元素类型相同，大小相等优点：存取速度很快缺点：实现必须知道数组的长度需要大块连续的内存快插入删除元素的效率极低空间通常是有限的2.2离散存储（链表）优点：空间没有限制插入删除元素很快缺点：存取速度很慢定义：n个节点离散分配彼此通过指针相连每个节点只有一个前驱节点，每个节点只有一个后续节点首节点没有前驱节点尾节点没有后续节点专业术语：首节点：第一个有效节点尾节点：最后一个有效节点头结点：第一个有效节点之前的那个节点，头结点并不存放有效数据，加头节点是为了方便对链表的操作，头结点的数据类型和首节点的数据类型一样头指针：指向头结点的指针变量尾指针：指向尾节点的指针变量如何确定一个链表需要几个参数？如果希望通过一个函数来对链表进行处理，我们至少要接受链表的哪些参数的问题只需要一个参数：头指针，因为通过头指针可以推算出链表的所有信息一个节点的生成：struct Node{int data;//数据域struct Node * pNext; //指针域}Node,*PNode; //Node等价于Struct Node,PNode等价于Struct NOde *类型2.3链表的分类：单链表：双链表：每一个节点有两个指针域循环链表：能通过任何一个节点找到其他所有的结点非循环链表：算法：遍历查找清空销毁求长度排序删除节点：r=p->pNext ; p->pNext = q; q->pNext = r;或者是q->pNext = p->pNext; p->pNext = q注意：p->pNext 表示p指向的那个节点的pNext成员插入节点3 各种数据结构的实现算法以及相关操作方法的实现3.1 实现顺序表的各种基本运算/*2012年2月20日22:32:41目的：实现顺序表中常用的9个操作方法，并实现测试之*/#include <stdio.h>#include <malloc.h>#define MaxSize 50typedef char ElemType;typedef struct{ElemType data[MaxSize];int length;} SqList;extern void InitList(SqList *&L); //形参的改变映射给实参extern void DestroyList(SqList *L);extern int ListEmpty(SqList *L);extern int ListLength(SqList *L);extern void DispList(SqList *L);extern int GetElem(SqList *L,int i,ElemType &e);extern int LocateElem(SqList *L, ElemType e);extern int ListInsert(SqList *&L,int i,ElemType e);extern int ListDelete(SqList *&L,int i,ElemType &e);int main(void){SqList *L;ElemType e;printf("\n=============顺序表中所有方法的实现===================\n"); printf(" (1)初始化顺序表L\n");InitList(L);printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");ListInsert(L,1,'a');ListInsert(L,2,'b');ListInsert(L,3,'c');ListInsert(L,4,'d');ListInsert(L,5,'e');printf(" (3)输出顺序表L:");DispList(L);printf(" (4)顺序表L长度=%d\n",ListLength(L));printf(" (5)顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));GetElem(L,3,e);printf(" (6)顺序表L的第3个元素=%c\n",e);printf(" (7)元素a的位置=%d\n",LocateElem(L,'a'));printf(" (8)在第4个元素位置上插入f元素\n");ListInsert(L,4,'f');printf(" (9)输出顺序表L:");DispList(L);printf(" (10)删除L的第3个元素\n");ListDelete(L,3,e);printf(" (11)输出顺序表L:");DispList(L);printf(" (12)释放顺序表L\n");DestroyList(L);return 0;}void InitList(SqList *&L){L=(SqList *)malloc(sizeof(SqList));L->length=0;}void DestroyList(SqList *L){free(L);}int ListEmpty(SqList *L){return(L->length==0);}int ListLength(SqList *L){return(L->length);}void DispList(SqList *L){int i;if (ListEmpty(L)) return;for (i=0;i<L->length;i++)printf(" %c ",L->data[i]);printf("\n");}int GetElem(SqList *L,int i,ElemType &e) {if (i<1 || i>L->length)return 0;e=L->data[i-1];return 1;}int LocateElem(SqList *L, ElemType e){int i=0;while (i<L->length && L->data[i]!=e) i++; if (i>=L->length)return 0;elsereturn i+1;}int ListInsert(SqList *&L,int i,ElemType e)int j;if (i<1 || i>L->length+1)return 0;i--; //将顺序表位序转化为elem下标*/ for (j=L->length;j>i;j--) //将data[i]及后面元素后移一个位置*/ L->data[j]=L->data[j-1];L->data[i]=e;L->length++; //顺序表长度增1*/return 1;}int ListDelete(SqList *&L,int i,ElemType &e){int j;if (i<1 || i>L->length)return 0;i--; //将顺序表位序转化为elem下标*/ e=L->data[i];for (j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];L->length--;return 1;}/*在VC++6.0中的输出结果为:=============顺序表中所有方法的实现===================(1)初始化顺序表L(2)依次采用尾插法插入a,b,c,d,e元素(3)输出顺序表L: a b c d e(4)顺序表L长度=5(5)顺序表L为非空(6)顺序表L的第3个元素=c(7)元素a的位置=1(8)在第4个元素位置上插入f元素(9)输出顺序表L: a b c f d e(10)删除L的第3个元素(11)输出顺序表L: a b f d e(12)释放顺序表LPress any key to continue总结：当调用DestroyList(L)后，free释放的事L指向的内存空间，但是此时，指针变量L仍然存在3.2 实现单链表的各种基本运算/*2012年2月22日19:05:12 作者：陈金林目的：实现单链表的基本方法，并实现之*/#include <stdio.h>#include <malloc.h>#define MaxSize 50typedef char ElemType;typedef struct LNode{ElemType data;struct LNode * next;}LinkList;void InitList(LinkList * &L);int ListInsert(LinkList * &L,int i,ElemType e);void DispList(LinkList * L);int ListLength(LinkList * L);int ListEmpty(LinkList * L);int GetElem(LinkList * L,int i,ElemType &e);int LocateElem(LinkList * L,ElemType e);int ListDelete(LinkList * &L,int i,ElemType &e);void DestroyList(LinkList * &L);int main(void){LinkList * h;ElemType e;printf("\n================实现单链表的常用操作============\n");printf("(1)初始化单链表h\n");InitList(h);printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");ListInsert(h,1,'a');ListInsert(h,2,'b');ListInsert(h,3,'c');ListInsert(h,4,'d');ListInsert(h,5,'e');printf("(3)输出单链表h");DispList(h);printf("(4)输出单链表h长度%d\n",ListLength(h));printf("(5)判断单链表h是否为空%s\n",(ListEmpty(h)==0)?"空":"非空"); GetElem(h,3,e);printf("(6)输出单链表h的第三个元素%d\n",e);printf("(7)输出元素'a'的位置%d\n",LocateElem(h,'a'));printf("(8)在第四个元素位置上插入'f'元素\n");ListInsert(h,4,'f');printf("(9)输出单链表h");DispList(h);printf("(10)删除h的第3个元素\n");ListDelete(h,3,e);printf("(11)输出单链表h :");DispList(h);printf("(12)释放单链表h\n");DestroyList(h);return 0;}void InitList(LinkList * &L){L = (LinkList *)malloc(sizeof(LinkList));L->next = NULL;}int ListInsert(LinkList * &L,int i,ElemType e){int j = 0;LinkList * p = L,* s;while(j<i-1 && p!=NULL){j++;p = p->next;}if(p == NULL)return 0;else{s = (LinkList *)malloc(sizeof(LinkList));s->data = e;s->next = p->next;p->next = s;return 1;}}void DispList(LinkList * L){LinkList * p = L->next;while(p!=NULL){printf(" %c ",p->data);p = p->next;}printf("\n");}int ListLength(LinkList * L){LinkList * p = L;int n = 0;while(p->next!=NULL){n++;p = p->next;}return(n);}int ListEmpty(LinkList * L){return (L->next == NULL);}int GetElem(LinkList * L,int i,ElemType &e) {int j = 0;LinkList * p = L;while(j<i && p!=NULL){j++;p = p->next;}if(p == NULL)return 0;else{e = p->data;return 1;}}int LocateElem(LinkList * L,ElemType e){LinkList * p = L->next;int i = 1;while(p!=NULL && p->data!=e){p = p->next;i++;}if(p == NULL)return (0);elsereturn (i);}int ListDelete(LinkList * &L,int i,ElemType &e) {int j= 0;LinkList * p = L,*q;while(j<i-1 && p!=NULL){j++;p = p->next;}if(p == NULL)return 0;else{q = p->next;if(q==NULL)return 0;e = q->data;p->next = q->next;free(q);return 1;}}void DestroyList(LinkList * &L){LinkList * p =L,* q=p->next;while(q!=NULL){free(p);p = q;q = p->next;}free(q);}/*在VC++6.0中的输出结果为:=======================实现单链表的常用操作=================(1)初始化单链表h(2)依次采用尾插法插入a,b,c,d,e元素(3)输出单链表h a b c d e(4)输出单链表h长度5(5)判断单链表h是否为空空(6)输出单链表h的第三个元素99(7)输出元素'a'的位置1(8)在第四个元素位置上插入'f'元素(9)输出单链表h a b c f d e(10)删除h的第3个元素(11)输出单链表h : a b f d e(12)释放单链表hPress any key to continue*/3.3 实现双链表的各种基本运算#include <stdio.h>#include <malloc.h>#define MaxSize 50typedef char ElemType;typedef struct DNode{ElemType data;struct DNode * prior;struct DNode * next;} DLinkList;extern void InitList(DLinkList *&L); //以下均为外部函数extern void DestroyList(DLinkList *&L);extern int ListEmpty(DLinkList *L);extern int ListLength(DLinkList *L);extern void DispList(DLinkList *L);extern int GetElem(DLinkList *L,int i,ElemType &e);extern int LocateElem(DLinkList *L,ElemType e);extern int ListInsert(DLinkList *&L,int i,ElemType e);extern int ListDelete(DLinkList *&L,int i,ElemType &e);int main(void){DLinkList * h;ElemType e;printf("\n========双链表所有操作方法的实现====作者：陈金林======\n");printf("(1)初始化双链表h\n");InitList(h);printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");ListInsert(h,1,'a');ListInsert(h,1,'b');ListInsert(h,1,'c');ListInsert(h,1,'d');ListInsert(h,1,'e');printf("(3)输出双链表h :");DispList(h);printf("(4)输出双链表h的长度%d\n",ListLength(h));printf("(5)双链表h为%s\n",(ListEmpty(h)?"空":"非空"));GetElem(h,3,e);printf("(6)输出双链表h的第3个元素%c\n",e);printf("(7)输出元素'a'的位置%d\n",LocateElem(h,'a'));printf("(8)在第4个元素的位置上插入'f'元素\n");printf("(9)输出双链表h:");DispList(h);printf("(10)删除h的第三个元素\n");ListDelete(h,3,e);printf("(11)输出双链表h:");DispList(h);printf("(12)释放双链表h\n");DestroyList(h);return 0;}void InitList(DLinkList *&L){L=(DLinkList *)malloc(sizeof(DLinkList)); //创建头结点L->prior=L->next=NULL;}void DestroyList(DLinkList *&L){DLinkList *p=L,*q=p->next;while (q!=NULL){free(p);p=q;q=p->next;}free(p);}int ListEmpty(DLinkList *L){return(L->next==NULL);}int ListLength(DLinkList *L){DLinkList *p=L;int i=0;while (p->next!=NULL){i++;p=p->next;}return(i);}void DispList(DLinkList *L){DLinkList *p=L->next;while (p!=NULL){printf(" %c ",p->data);p=p->next;}printf("\n");}int GetElem(DLinkList *L,int i,ElemType &e) {int j=0;DLinkList *p=L;while (j<i && p!=NULL){j++;p=p->next;}if (p==NULL)return 0;else{e=p->data;return 1;}}int LocateElem(DLinkList *L,ElemType e){int n=1;DLinkList *p=L->next;while (p!=NULL && p->data!=e){n++;p=p->next;}if (p==NULL)return(0);elsereturn(n);}int ListInsert(DLinkList *&L,int i,ElemType e){int j=0;DLinkList *p=L,*s;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) //未找到第i-1个结点return 0;else //找到第i-1个结点*p{s=(DLinkList *)malloc(sizeof(DLinkList)); //创建新结点*ss->data=e;s->next=p->next; //将*s插入到*p之后if (p->next!=NULL) p->next->prior=s;s->prior=p;p->next=s;return 1;}}int ListDelete(DLinkList *&L,int i,ElemType &e){int j=0;DLinkList *p=L,*q;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) //未找到第i-1个结点return 0;else //找到第i-1个结点*p{q=p->next; //q指向要删除的结点if (q==NULL) return 0; //不存在第i个结点e=q->data;p->next=q->next; //从单链表中删除*q结点if (p->next!=NULL) p->next->prior=p;free(q); //释放*q结点return 1;}}3.4 实现循环单链表的各种基本运算/*2012年2月24日20:57:59 作者：陈金林目的：循环单链表所有方法的实现*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct LNode //定义循环单链表结点类型{ElemType data;struct LNode *next;} LinkList;void InitList(LinkList *&L);void DestroyList(LinkList *&L);int ListEmpty(LinkList *L);int ListLength(LinkList *L);void DispList(LinkList *L);int GetElem(LinkList *L,int i,ElemType &e);int LocateElem(LinkList *L,ElemType e);int ListInsert(LinkList *&L,int i,ElemType e);int ListDelete(LinkList *&L,int i,ElemType &e);int main(void){LinkList * h;ElemType e;printf("\n==========循环单链表所有方法的实现=====================\n"); printf(" (1)初始化循环单链表h\n");InitList(h);printf(" (2)依次采用头插法插入a,b,c,d,e元素\n");ListInsert(h,1,'a');ListInsert(h,1,'b');ListInsert(h,1,'c');ListInsert(h,1,'d');ListInsert(h,1,'e');printf(" (3)输出循环单链表h:");DispList(h);printf(" (4)输出循环单链表h长度length = %d\n",ListLength(h));printf(" (5)判断循环单链表h是否为空? %s\n",ListEmpty(h)?"空":"非空"); GetElem(h,3,e);printf(" (6)输出循环单链表h的第3个元素%c\n",e);printf(" (7)输出元素'a'的位置:%d\n",LocateElem(h,'a'));printf(" (8)在第四个元素位置上插入'f'元素\n");ListInsert(h,4,'f');printf(" (9)输出循环单链表h :");DispList(h);printf(" (10)删除L的第3个元素\n");ListDelete(h,3,e);printf(" (11)输出循环单链表h :");DispList(h);printf(" (12)释放循环单链表h\n");DestroyList(h);return 0;}void InitList(LinkList *&L){L=(LinkList *)malloc(sizeof(LinkList)); //创建头结点L->next=L; //说名此链表为循环单链表}void DestroyList(LinkList *&L){LinkList *p=L,*q=p->next;while (q!=L){free(p);p=q;q=p->next;}free(p);}int ListEmpty(LinkList *L){return(L->next==L);}int ListLength(LinkList *L){LinkList *p=L;int i=0;while (p->next!=L){i++;p=p->next;}return(i);}void DispList(LinkList *L){LinkList *p=L->next;while (p!=L){printf(" %c ",p->data);p=p->next;}printf("\n");}int GetElem(LinkList *L,int i,ElemType &e){int j=0;LinkList *p;if (L->next!=L) //单链表不为空表时{if (i==1){e=L->next->data;return 1;}else //i不为1时{p=L->next;while (j<i-1 && p!=L){j++;p=p->next;}if (p==L)return 0;else{e=p->data;return 1;}}}else //单链表为空表时return 0;}int LocateElem(LinkList *L,ElemType e) {LinkList *p=L->next;int n=1;while (p!=L && p->data!=e){p=p->next;n++;}if (p==L)return(0);elsereturn(n);}int ListInsert(LinkList *&L,int i,ElemType e) {int j=0;LinkList *p=L,*s;if (p->next==L || i==1) //原单链表为空表或i==1时{s=(LinkList *)malloc(sizeof(LinkList));//创建新结点*ss->data=e;s->next=p->next; //将*s插入到*p之后p->next=s;return 1;}else{p=L->next;while (j<i-2 && p!=L){j++;p=p->next;}if (p==L) //未找到第i-1个结点return 0;else //找到第i-1个结点*p{s=(LinkList *)malloc(sizeof(LinkList));//创建新结点*ss->data=e;s->next=p->next; //将*s插入到*p之后p->next=s;return 1;}}}int ListDelete(LinkList *&L,int i,ElemType &e){int j=0;LinkList *p=L,*q;if (p->next!=L) //原单链表不为空表时{if (i==1) //i==1时{q=L->next; //删除第1个结点e=q->data;L->next=q->next;free(q);return 1;}else //i不为1时{p=L->next;while (j<i-2 && p!=L){j++;p=p->next;}if (p==L) //未找到第i-1个结点return 0;else //找到第i-1个结点*p{q=p->next; //q指向要删除的结点e=q->data;p->next=q->next; //从单链表中删除*q结点free(q); //释放*q结点return 1;}}}else return 0;}/*在VC++6.0中的输出结果为:=================循环单链表所有方法的实现=====================(1)初始化循环单链表h(2)依次采用头插法插入a,b,c,d,e元素(3)输出循环单链表h: e d c b a(4)输出循环单链表h长度length = 5(5)判断循环单链表h是否为空? 非空(6)输出循环单链表h的第3个元素c(7)输出元素'a'的位置:5(8)在第四个元素位置上插入'f'元素(9)输出循环单链表h : e d c f b a(10)删除L的第3个元素(11)输出循环单链表h : e d f b a(12)释放循环单链表hPress any key to continue*/3.5 实现循环双链表的各种基本运算/*2012年2月24日21:01:46 作者：陈金林目的：循环双链表所有方法的实现*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct DNode //定义双链表结点类型{ElemType data;struct DNode *prior; //指向前驱结点struct DNode *next; //指向后继结点} DLinkList;void InitList(DLinkList *&L);void DestroyList(DLinkList *&L);int ListEmpty(DLinkList *L);int ListLength(DLinkList *L);void DispList(DLinkList *L);int GetElem(DLinkList *L,int i,ElemType &e);int LocateElem(DLinkList *L,ElemType e);int ListInsert(DLinkList *&L,int i,ElemType e);int ListDelete(DLinkList *&L,int i,ElemType &e);int main(void){DLinkList * h;ElemType e;printf("\n=================循环双链表所有方法的实现=====================\n");printf(" (1)初始化循环双链表h\n");InitList(h);printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");ListInsert(h,1,'a');ListInsert(h,1,'b');ListInsert(h,1,'c');ListInsert(h,1,'d');ListInsert(h,1,'e');printf(" (3)输出循环双链表h:");DispList(h);printf(" (4)输出循环双链表h长度length = %d\n",ListLength(h));printf(" (5)判断循环双链表h是否为空? %s\n",ListEmpty(h)?"空":"非空");GetElem(h,3,e);printf(" (6)输出循环双链表h的第3个元素%c\n",e);printf(" (7)输出元素'a'的位置:%d\n",LocateElem(h,'a'));printf(" (8)在第四个元素位置上插入'f'元素\n");ListInsert(h,4,'f');printf(" (9)输出循环双链表h :");DispList(h);printf(" (10)删除L的第3个元素\n");ListDelete(h,3,e);printf(" (11)输出循环双链表h :");DispList(h);printf(" (12)释放循环双链表h\n");DestroyList(h);return 0;}void InitList(DLinkList *&L){L=(DLinkList *)malloc(sizeof(DLinkList)); //创建头结点L->prior=L->next=L;}void DestroyList(DLinkList *&L){DLinkList *p=L,*q=p->next;while (q!=L){free(p);p=q;q=p->next;}free(p);}int ListEmpty(DLinkList *L){return(L->next==L);}int ListLength(DLinkList *L){DLinkList *p=L;int i=0;while (p->next!=L){i++;p=p->next;}return(i);}void DispList(DLinkList *L){DLinkList *p=L->next;while (p!=L){printf(" %c ",p->data);p=p->next;}printf("\n");}int GetElem(DLinkList *L,int i,ElemType &e) {int j=0;DLinkList *p;if (L->next!=L) //双链表不为空表时{if (i==1){e=L->next->data;return 1;}else //i不为1时{p=L->next;while (j<i-1 && p!=L){j++;p=p->next;}if (p==L)return 0;else{e=p->data;return 1;}}}else //双链表为空表时return 0;}int LocateElem(DLinkList *L,ElemType e) {int n=1;DLinkList *p=L->next;while (p!=NULL && p->data!=e){n++;p=p->next;}if (p==NULL)return(0);elsereturn(n);}int ListInsert(DLinkList *&L,int i,ElemType e){int j=0;DLinkList *p=L,*s;if (p->next==L) //原双链表为空表时{s=(DLinkList *)malloc(sizeof(DLinkList)); //创建新结点*ss->data=e;p->next=s;s->next=p;p->prior=s;s->prior=p;return 1;}else if (i==1) //原双链表不为空表但i=1时{s=(DLinkList *)malloc(sizeof(DLinkList)); //创建新结点*ss->data=e;s->next=p->next;p->next=s; //将*s插入到*p之后s->next->prior=s;s->prior=p;return 1;}else{p=L->next;while (j<i-2 && p!=L){ j++;p=p->next;}if (p==L) //未找到第i-1个结点return 0;else //找到第i-1个结点*p{s=(DLinkList *)malloc(sizeof(DLinkList)); //创建新结点*ss->data=e;s->next=p->next; //将*s插入到*p之后if (p->next!=NULL) p->next->prior=s;s->prior=p;p->next=s;return 1;}}}int ListDelete(DLinkList *&L,int i,ElemType &e){int j=0;DLinkList *p=L,*q;if (p->next!=L) //原双链表不为空表时{if (i==1) //i==1时{q=L->next; //删除第1个结点e=q->data;L->next=q->next;q->next->prior=L;free(q);return 1;}else //i不为1时{p=L->next;while (j<i-2 && p!=NULL){j++;p=p->next;}if (p==NULL) //未找到第i-1个结点return 0;else //找到第i-1个结点*p{q=p->next; //q指向要删除的结点if (q==NULL) return 0; //不存在第i个结点e=q->data;p->next=q->next; //从单链表中删除*q结点if (p->next!=NULL) p->next->prior=p;free(q); //释放*q结点return 1;}}}else return 0; //原双链表为空表时}/*在VC++6.0中的输出结果为:=================循环双链表所有方法的实现=====================(1)初始化循环双链表h(2)依次采用尾插法插入a,b,c,d,e元素(3)输出循环双链表h: e d c b a(4)输出循环双链表h长度length = 5(5)判断循环双链表h是否为空? 非空(6)输出循环双链表h的第3个元素c(7)输出元素'a'的位置:5(8)在第四个元素位置上插入'f'元素(9)输出循环双链表h : e d c f b a(10)删除L的第3个元素(11)输出循环双链表h : e d f b a(12)释放循环双链表hPress any key to continue*/三．线性结构的常见应用之一------------------栈定义:一种可以实现'先进后出' 的存储结构。

第一章绪论1、数据结构是计算机中存储、组织数据的方式。

精心选择的数据结构可以带来最优效率的算法。

2、程序设计= 算法+数据结构3、解决问题方法的效率：跟数据的组织方式有关跟空间的利用效率有关跟算法的巧妙程度有关4、数据：所有能输入到计算机中,且被计算机处理的符号的集合，是计算机操作对象的总称；是计算机处理的信息的某种特定的符号表示形式。

5、数据元素：数据中的一个“个体” ,数据结构中讨论的基本单位。

相当于“记录” ,在计算机程序中通常作为一个整体考虑和处理。

6、数据项: 相当于记录的“域”, 是数据的不可分割的最小单位如学号。

数据元素是数据项的集合。

7、数据对象：性质相同的数据元素的集合.例如: 所有运动员的记录集合8、数据结构：是相互间存在某种关系的数据元素集合。

9、数据结构是带结构的数据元素的集合。

10、不同的关系构成不同的结构。

11、次序关系：{vai,ai+1>|i=1,2,3,4,5,6}12、 对每种数据结构，主要讨论如下两方面的问题：1） 数据的逻辑结构，数据结构的基本操作；2） 数据的存储结构，数据结构基本操作的实现；13、 数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。

数据结构的基本操作：指对数据结构的加工处理。

14、 数据的存储结构（物理结构）:数据结构在计算机内存中的表示。

数据结构基本操作的实现：基本操作在计算机上的实现（方法）。

15、数据结构的有关概念|线性表「上线性结构!栈［队（仁数据的逻辑结构=i B.非彌結构I 树形结构 J I 图形结构木数据的存储结枸I A 噸序行储 B 链式存储 < 3、数据的运算：檢索.插入.删除*烽改等16、数据元素的 4 类的基本结构 ：① 集合； 数£结构的三个方廁②线性结构：结构中数据元素之间存在一对一的关系；③树形结构：结构中数据元素之间存在一对多的关系；②4 图状结构或网状结构：结构中数据元素之间存在多对多的关系。

数据结构教案第一章概论教学时间：3学时教学目的：1、理解数据结构的基本概念和术语；2、理解抽象数据类型的表示与实现；3、掌握算法和算法分析。

教学内容：什么是数据、数据元素、数据对象、数据结构、逻辑结构和存储结构、数据类型、抽象数据类型、算法的定义、算法的特性、算法的时空代价1.1基本概念和术语数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入计算机中并被计算机程序处理的符号的总称。

它是计算机程序加工的“原料”。

例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的对象是字符串。

因此，对计算机而言，数据的含义极为广泛，如图象，声音等都可以通过编码而归数据的范畴数据元素(data element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

有时，一个数据元素可由若干个数据项组成。

数据项是不可分割的最小单位。

数据对象(data object)：是性质相同的数据元素的集合，是数据的一个子集。

数据结构(data structure)：是相互之间存在一种或多种特定关系的数据元素的集合。

数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(structure)。

包括三方面内容：(1)数据元素之间的逻辑关系，也称为数据的逻辑结构；(2)数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；(3)数据的运算，即对数据施加的操作。

数据的逻辑结构：是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机，包括两大类：(1)线性结构：特征是有且仅有一个开始结点和一个终端结点，其余的结点有且仅有一个直接前趋和一个直接后继。

如：线性表、栈、队列。

(2)非线性结构：特征是一个结点可能有多个直接前趋和直接后继。

如：广义表、树、图。

数据的存储结构：是逻辑结构用计算机语言的实现。

有四种存储方式：(1)顺序存储方法：是用一组连续的存储单元把逻辑上相邻的结点存储在物理位置上相邻的存储单元里；(2)链式存储方法：是用一组不一定连续的存储单元存储逻辑上相邻的结点，结点间的逻辑关系是由附加的指针域表示的。

第1 章绪论本章主要介绍以下内容1、数据结构中涉及的基本概念、术语及所研究的主要内容2、本教材使用的描述工具本章重点和难点：1、数据结构、数据类型、ADT、算法等重要概念。

用计算机求解任何问题都离不开程序设计，而程序设计的实质是数据表示和数据处理。

数据要能被计算机处理，首先必须能够存储在计算机的内存中，这项任务称为数据表示，数据表示的核心任务是数据结构的设计；一个实际问题的求解必须满足各项处理要求，这项任务称为数据处理，数据处理的核心任务是算法设计。

数据结构课程主要讨论数据表示和数据处理的基本问题。

本章将概括地介绍数据结构的基本概念、基本思想和基本方法。

1.1 数据结构的兴起和发展数据结构起源于程序设计。

随着计算机科学与技术的不断发展，计算机的应用领域已不再局限于科学计算，而更多地应用于控制、管理等非数值处理领域。

与此相应，计算机处理的数据也由纯粹的数值发展到字符、表格、图形、图象、声音等具有一定结构的数据，处理的数据量也越来越大，这就给程序设计带来一个问题：应如何组织待处理的数据以及数据之间的关系（结构）。

1968 年克努思教授[1]开创了数据结构的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。

70 年代初，数据结构作为一门独立的课程开始进入大学课堂。

数据结构随着程序设计的发展而发展。

程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段：⑴无结构阶段。

40~60 年代，计算机的应用主要针对科学计算，程序设计技术以机器语言/ 汇编语言为主，程序处理的数据是纯粹的数值，数据之间的关系主要是数学公式或数学模型。

这一阶段，在人类的自然语言与计算机编程语言之间存在着巨大的鸿沟，程序设计属于面向计算机的程序设计，设计人员关注的重心是使程序尽可能地被计算机接受并按指令正确执行，至于程序能否让人理解并不重要。