线性表
线性表的定义
定义n个数据元素的有限序列，记作（a1, a2, …, an）ai 是表中数据元素，n 是表长度
线性表的特点
除第一个元素外，其他每一个元素有一个且仅有一个
直接前驱。
除最后一个元素外其他每一个元素有一个且仅有一个
直接后继。
顺序表的定义和特点
定义：将线性表中的元素相继存放在一个连续的存储空间中。
可利用一维数组描述存储结构。
特点：线性表的顺序存储方式。
遍历：顺序访问, 可以随机存取。
链表
特点
每个元素(表项)由结点(Node)构成。
线性结构
结点可以连续，可以不连续存储
结点的逻辑顺序与物理顺序可以不一致
表可扩充
typedef char ListData; typedef struct node { //链表结点 ListData data; //结点数据域 struct node * link; //结点链域 } ListNode; typedef ListNode * LinkList; LinkList first; //链表头指针
链表的插入与删除
插入
int Insert ( LinkList& first, int x, int i ) { ListNode * p = first; int k = 0; //在链表第 i 个结点处插入新元素 x while ( p != NULL && k < i -1 ) { p = p->link; k++; } //找第 i-1个结点 if ( p == NULL && first != NULL ) { printf ( “无效的插入位置! ” ); return 0; } ListNode * newnode = (ListNode *) malloc ( sizeof (ListNode) ); //创建新结点 newnode->data = x; if ( first == NULL || i == 1 ) { //插在表前 newnode->link = first; first = newnode; }else { //插在表中或末尾 newnode->link = p->link; p->link = newnode; } return 1; }
删除
int Delete ( LinkList& first, int i ) { ListNode *p, *q; //在链表中删除第 i 个结点 if ( i == 1 ) //删除表中第 1 个结点 { q = first; first = first->link; } else { p = first; int k = 0; //找第 i-1个结点 while ( p != NULL && k < i-1 ) { p = p->link; k++; } if ( p == NULL || p->link == NULL ) { printf ( “无效的删除位置! ” ); return 0; } else { //删除表中或表尾元素 q = p->link; //重新链接 p->link = q->link; } } free ( q ); //删除q return 1; }
循环链表
typedef char ListData; typedef struct cnode { //链表结点 ListData data; //结点数据域 struct cnode * link; //结点链域 } CircListNode; typedef CircListNode * CircLinkList; //循环链表头指针 CircLinkList first; //循环链表头指针
双向循环链表
typedef int ListData; typedef struct dnode { ListNode data; //数据 struct dnode * prior, * next; //指针 } DblNode; typedef DblNode * DblList; //双向链表 void CreateDblList ( DblList *first ) { first = ( DblNode * ) malloc ( sizeof ( DblNode ) ); if ( first == NULL ) { print ( “存储分配错! ” ); exit (1); } first->prior = first->next = first; //表头结点的链指针指向自己 }