线性表的链式表示 1、 单链表的定义:
描述代码: Typedef struct LNode{ Elemtype data; //数据域 Struct LNode *next;//指针域 }LNode,*LinkList;
2、 单链表上基本操作的实现 1、 采用头插法建立单链表:将读取的数据存在新节点数据中,然后将新节点插入到当前链表的表头。
描述代码: LinkList CreatList1(LinkList &L){ LNode s;int x; L=(LinkList)malloc(sizeof(LNode)); //创建头结点 L->next=NULL; //初始化为空链表 Scanf(“%d”,&x); //输入节点的值 While(x!=9999){ s = (LNode)malloc(sizeof(LNode)); s->data=x; s->next=L->next; L->next=s; Scanf(“%d”,&x); } Return L; } 特点:读入数据如链表数据相反,时间复杂度为O(n)
2、 采用尾插法建立单链表 将新节点插入到当前链表的表尾上,顺序与读入顺序相同,需要在增加尾指针r.
描述代码: LinkList CreatList2(LinkList &L){ //从表头到表尾正向建立单链表L,每次均在表尾插入元素 Int x; L=(LinkList)malloc(sizeof(LNode)); LNode *s,*r=L; //r为表尾指针 Scanf(“%d”,&x); //输入节点值 While(x!=9999){ //9999表示结束 S=(LNode *)malloc(sizeof(LNode)); s->data=x; r->next=s; //r指向新的表尾节点 r=s; scanf(“%d”,&x); } r->next=NULL; //尾节点指针置空 return L; } 时间复杂度O(n)
3、 按序号查找节点值:从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点的指针域NULL. 描述代码 LNode *GetElem(LinkList L,int i){ Int j=1;//计数,初始为1 LNode *p=L-next; //头结点指针赋给p If(i==0) return L;//若i等于0返回头结点 If(idata!=e){ P=p->nest; } Return p; } 时间复杂度 O(n) 5、 插入结点操作:将值为x的结点插入到单链表的第i个位置上。
描述代码 p=GetElem(L,i-1);//查找插入位置的前驱结点 s->next=p-next; p->next=s; 时间复杂度:O(n)
把新增结点插入到*P之前,描述代码
s->next=p-next; //修改指针 p->next=s; temp=p->data; //交换数据域 p->data=s->data; s->data=temp; 6、 删除结点操作:删除第i个结点。查找第i-1个点,在修改指针。
描述代码: P=GetElem(L,i-1); //获得前驱结点 q=p->next; p->next=q->next; free(q); //释放内存 时间复杂度O(n) 删除*P本身结点 q=p->next; p->data=p->next->data; p->next=q->next; free(q);
求表长:从头结点开始计数,直到指针指向NULL返回i。 int *LocateElem(LinkList L){ LNode *p=L-next; Int i =0; While(p!=NULL){ p=p->nest; i++; } Return i; }