线性表

发表于 | 更新于: | 分类于 |
| 字数统计: 549 | 阅读时长 ≈ 2
���Ľ�������л�����Ķ�

头结点

头结点1
头结点
线性链表的结点类型定义

1
2
3
4
typedef struct Lnode{
   ElemType   data;    
   Struct  Lnode  *next;
}Lnode  *linklist;

说明：
LNode：结构类型名；
LNode：类型结构变量有两个域：
data：存放线性表的数据元素，
next：存放元素直接后继结点的地址;
该类型结构变量用于表示线性链表中的一个结点；
LNODE *p;：p为指向结点(结构)的指针变量；
p是LNODE类型的指针变量

建表

头插法建立单链表L

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Linklist CreateFromHead(){
  L = (Linklist)malloc(sizeof(LNode));
  L->next = NULL;
  while(flag){
    c = getchar();
    if(c!='$'){
      s = (LNode*)malloc(sizeof(LNode));
      s->data = c;
      s->next = L->next;
      L->next = s;
    }else
      flag = 0;
  }
  return L;
}

插入

插入的主要内容如下：

1
2
3
4
q=(LNode*)malloc(sizeof(LNode));
q->data = 'a';
q->next = p->next;
p->next = q;

插入

删除

1
2
3
q = p->next;
p->next = q->next;
free(q);

插入、删除算法中的循环条件为何不同？
删除算法中的循环条件（p->next! =NULL && k<i-1）与前面插入算法中的循环条件（p! =NULL && k<i-1）不同，因为前面插入算法时的插入位置有m+1个（m为当前单链表中数据元素的个数）。i=m+1是指在第m+1个位置前插入，即在单链表的末尾插入。而删除操作中删除的合法位只有m个，若使用与前面插入操作相同的循环条件，则会出现指针指空的情况， 使删除操作失败。

循环链表的定义
将线性链表的最后一个结点的指针指向链表的第一个结点（是一个首尾相连的单链表）
循环链表与线性链表操作的主要差别？
循环链表与线性链表操作的主要差别是算法中循环结束的条件不是p或p->next是否为NULL,而是它们是否等于头指针；
双向链表的定义
双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。

1
2
3
4
typedef struct DNode{ 
	ElemType data; 
	struct DNode *prior,*next;
}DNode,*DoubleList;

0%