数据结构之线性表（链式表示之单链表）

Bertha 。 2023-07-16 03:49 132阅读 0赞

定义： 线性表的链式存储又称单链表

  1. typedef struct LNode{ 
  2. ElemType data;
  3. struct LNode *next;
  4. }LNode,*LinkList;

基本操作：
头插法建立单链表：

  1. LinkList List_HeadInsert(LinkList &L){ 
  2. LNode *s;int x;
  3. L=(LinkList)malloc(sizeof(LNode));
  4. L->next=NULL;
  5. scanf("%d",&x);
  6. while(x!=9999){ 
  7. s=(LNode*)malloc(sizeof(LNode));
  8. s->data=x;
  9. s->next=L->next;
  10. L->next=s;
  11. scanf("%d",&x);
  12. }
  13. return L;
  14. }

最坏时间复杂度：O(n)

尾插法建立单链表：

  1. LinkList List_TailInsert(LinkList &L){ 
  2. int x;
  3. L=(LinkList)malloc(sizeof(LNode));
  4. LNode *s,*r=L;
  5. scanf("%d",&x);
  6. while(x!=9999){ 
  7. s=(LNode*)malloc(sizeof(LNode));
  8. s->data=x;
  9. r->next=s;
  10. r=s;
  11. scanf("%d",&x);
  12. }
  13. r->next=NULL;
  14. return L;
  15. }

最坏时间复杂度：O(n)

按序号查找操作：

  1. LNode *GetElem(LinkList L,int i){ 
  2. int j=1;
  3. LNode *p=L->next;
  4. if(i==0)
  5. return L;
  6. if(i<1)
  7. return NULL;
  8. while(p&&j<i){ 
  9. p=p->next;
  10. j++;
  11. }
  12. return p;
  13. }

最坏时间复杂度：O(n)

按值查找操作：

  1. LNode *LocateElem(LinkList L,ElemType e){ 
  2. LNode *p=L->next;
  3. while(p!=NULL&&p->data!=e)
  4. p=p->next;
  5. return p;
  6. }

最坏时间复杂度：O(n)

插入节点操作：

  1. p=GetElem(L,i-1);
  2. s->next=p->next;
  3. p->next=s;

删除节点操作：

  1. p=GetElem(L,i-1);
  2. q=p->next;
  3. p->next=q->next;
  4. free(q);

(优化)删除给定节点 *p：

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

求表长：

  1. int k=0;
  2. p=head;
  3. while(p->next!=NULL){ 
  4. k++;
  5. p=p->next;
  6. }

发表评论

表情：
评论列表 （有 0 条评论，132人围观）

还没有评论，来说两句吧...

相关阅读

    相关 线性表链式表示和实现

    1、我们把存储数据元素信息的域称为数据域，把存储直接后继的域称为指针域。指针域中存储的信息称为指针或链。元素（数据元素映像）+指针（指示后继元素存储位置）=结点（表示数据元素）

    男娘i男娘i/ 0 赞/ 315 阅读