精华内容
下载资源
问答
  • 对于一个不带头节点的单链表
    2021-05-22 14:05:31

    不带头结点的单链表结构体声明

    typedef struct Node

    {

    int data;

    struct Node *next;

    }Node, *LinkList;

    (1)初始化

    void InitLinkList(LinkList *plist) //plist为二级指针,主函数传递第一个结点指针的地址

    {

    assert(plist!=NULL);

    if(plist == NULL)

    return;

    *plist = NULL;

    }

    (2)求链表长度

    int ListLength(LinkList plist) //不需要修改链表,则只需传递一级指针

    {

    int count=0;

    while(plist != NULL)

    {

    count++;

    plist=plist->next;

    }

    return count;

    }

    (3)得到某个结点,函数返回该结点

    LinkList GetNode(LinkList plist, int pos)

    {

    assert(plist!=NULL);

    if(plist == NULL)

    return NULL;

    LinkList p=plist;

    while(pos > 1) //pos为1即找到该位置,链表是从第一个结点算起

    {

    p=p->next;

    pos--;

    }

    return p;

    }

    (4)静态函数:申请结点空间

    static LinkList NodeApply(LinkList next, int val)

    {

    LinkList q=(Node *)malloc(sizeof(Node));

    assert(q != NULL);

    if (q == NULL)

    return NULL;

    q->data=val;

    q->next=next;

    return q;

    }

    (5)插入

    void Insert(LinkList *plist, int pos, int val)

    {

    assert(plist!=NULL);

    if(plist == NULL)

    return;

    if(pos < 0 || pos >ListLength(*plist))

    return;

    if(pos == 0) //头插要单独考虑

    {

    *plist=NodeApply(*plist,val); //即*plist指向新节点

    return;

    }

    LinkList p=GetNode(*plist, pos); //要插入其后的结点的位置

    p->next=NodeApply(p->next, val);

    }

    (6)头插

    void InsertHead(LinkList *plist, int val)

    {

    assert(plist!=NULL);

    if(plist == NULL)

    return;

    *plist=NodeApply(*plist,val);

    }

    (7)尾插

    void InsertTail(LinkList *plist, int val)

    {

    assert(plist!=NULL);

    if(plist == NULL)

    return;

    Insert(plist, ListLength(*plist), val);

    }

    (8)输出

    void Show(LinkList plist)

    {

    for(Node *p=plist; p!=NULL; p=p->next)

    {

    printf("%d -->",p->data);

    }

    printf("NULL\n");

    }

    (9)删除

    void Delete(LinkList *plist, int pos)

    {

    assert(plist != NULL);

    if(plist == NULL)

    {

    return;

    }

    if(pos<=0 || pos>ListLength(*plist))

    {

    return;

    }

    if(pos == 1) //头删特殊考虑

    {

    LinkList p=*plist;

    *plist=p->next;

    free(p);

    return;

    }

    LinkList p=GetNode(*plist, pos-1); //要删除结点的前一个结点

    LinkList q=p->next; //要删除的结点

    p->next=q->next;

    free(q);

    }

    (10)头删

    void DeleteHead(LinkList *plist)

    {

    assert(plist != NULL);

    if(plist == NULL)

    {

    return;

    }

    LinkList p=*plist;

    *plist=p->next;

    free(p);

    }

    (11)尾删

    void DeleteTail(LinkList *plist)

    {

    assert(plist != NULL);

    if(plist == NULL)

    {

    return;

    }

    Delete(plist,ListLength(*plist));

    }

    (12)判空

    int ListEmpty(LinkList plist)

    {

    if(plist == NULL) //第一个结点指针指向空

    return -1; //为空

    return 0;

    }

    (13)链表清空

    void ClearList(LinkList *plist)

    {

    assert(plist != NULL);

    if(plist == NULL)

    {

    return;

    }

    while(!ListEmpty(*plist)) //只要不为空

    {

    DeleteHead(plist);//头删

    }

    }

    主函数

    int main()

    {

    LinkList plist; //栈区定义一个结点指针类型

    InitLinkList(&plist);

    Insert(&plist,0,10);

    Insert(&plist,0,20);

    Insert(&plist,0,30);

    Insert(&plist,1,40);

    InsertHead(&plist,50);

    InsertTail(&plist,60);

    Show(plist);

    DeleteTail(&plist);

    Show(plist);

    ClearList(&plist);

    Show(plist);

    }

    更多相关内容
  • 带头结点单链表 和 不带头结点单链表的区别: 带头结点单链表,在进行插入、删除操作时,不需要改变链表头指针。 不带头结点的单链表,在进行插入、删除操作时,可能会涉及到链表头指针的修改(所以链表作为参数...

    下面的代码中,传递链表时,传的是头指针。如果是带头结点的链表,传递链表时,可以传头结点,具体可以看看 C语言实现-线性表的链式存储(单链表)


    带头结点单链表 和 不带头结点单链表的区别:

    • 带头结点单链表,在进行插入、删除操作时,不需要改变链表头指针。

    • 不带头结点的单链表,在进行插入、删除操作时,可能会涉及到链表头指针的修改(所以链表作为参数传递时,传递的是头指针的引用,具体可看代码④中head_insert方法中的指针变量带了&取地址符,而代码⑤中的没有。因为带头结点单链表进行头插操作需要修改头指针,而不带头结点的单链表进行头插操作时不需要修改头指针

    • 具体的代码也有些许差异,可对比 代码④ 和 代码⑤

    带头结点单链表 和 不带头结点的init()初始化都修改了头指针,所以指针变量带了&取地址符



    不带头结点的操作

    ① ② ③ ④ 四组代码本质是一样的。只是我本人对地址、指针、引用、指针变量概念不是很理解,所以才写了这四组代码进行对比,方便自己以后复习理解。读者可以跳过① ② ③,直接看④的代码即可

    代码①

    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct LNode {
    	int data;
    	struct LNode *next;
    };
    
    
    void init(LNode **L) {
    	*L = NULL;
    }
    
    
    void head_insert(LNode **L, int x) {
    	LNode *newP = (LNode *)malloc(sizeof(LNode));
    	newP->data = x;
    	
    	newP->next = *L;
    	*L = newP;
    }
    
    
    LNode *get(LNode *L, int k) {
    	if (k < 1) {
    		printf("查找位置非法!");
    		return NULL;
    	}
    	int i = 1;
    	if (L != NULL && i <= k) {
    		L = L->next;
    		i++;
    	}
    	if (i == k) {
    		return L;
    	}
    	printf("查找位置非法!");
    	return NULL;
    }
    
    
    void print(LNode *L) {
    	printf("\n");
    	while (L) {
    		printf("%4d ", L->data);
    		L = L->next;
    	}
    	printf("\n");
    }
    
    
    int main() {
    	LNode *L;
    	init(&L);
    	head_insert(&L, 15);
    	head_insert(&L, 25);
    	head_insert(&L, 35);
    	print(L);
    	printf("\n%4d \n", get(L, 2)->data);
    	return 0;
    }
    

    代码②

    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct LNode {
    	int data;
    	struct LNode *next;
    };
    
    
    void init(LNode *&L) {
    	L = NULL;
    }
    
    
    void head_insert(LNode *&L, int x) {
    	LNode *newP = (LNode *)malloc(sizeof(LNode));
    	newP->data = x;
    	
    	newP->next = L;
    	L = newP;
    }
    
    
    LNode *get(LNode *L, int k) {
    	if (k < 1) {
    		printf("查找位置非法!");
    		return NULL;
    	}
    	int i = 1;
    	if (L != NULL && i <= k) {
    		L = L->next;
    		i++;
    	}
    	if (i == k) {
    		return L;
    	}
    	printf("查找位置非法!");
    	return NULL;
    }
    
    
    void print(LNode *L) {
    	printf("\n");
    	while (L) {
    		printf("%4d ", L->data);
    		L = L->next;
    	}
    	printf("\n");
    }
    
    
    int main() {
    	LNode *L;
    	init(L);
    	head_insert(L, 15);
    	head_insert(L, 25);
    	head_insert(L, 35);
    	print(L);
    	printf("\n%4d \n", get(L, 2)->data);
    	return 0;
    }
    

    代码③

    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct LNode {
    	int data;
    	struct LNode *next;
    }*LinkList;
    
    
    void init(LinkList *L) {
    	*L = NULL;
    }
    
    
    void head_insert(LinkList *L, int x) {
    	LinkList newP = (LinkList)malloc(sizeof(LNode));
    	newP->data = x;
    	
    	newP->next = *L;
    	*L = newP;
    }
    
    
    LinkList get(LinkList L, int k) {
    	if (k < 1) {
    		printf("查找位置非法!");
    		return NULL;
    	}
    	int i = 1;
    	if (L != NULL && i <= k) {
    		L = L->next;
    		i++;
    	}
    	if (i == k) {
    		return L;
    	}
    	printf("查找位置非法!");
    	return NULL;
    }
    
    
    void print(LinkList L) {
    	printf("\n");
    	while (L) {
    		printf("%4d ", L->data);
    		L = L->next;
    	}
    	printf("\n");
    }
    
    
    int main() {
    	LinkList L;
    	init(&L);
    	head_insert(&L, 15);
    	head_insert(&L, 25);
    	head_insert(&L, 35);
    	print(L);
    	printf("\n%4d \n", get(L, 2)->data);
    	return 0;
    }
    

    代码④

    #include <stdio.h>
    #include <malloc.h>
    
    //结构体
    typedef struct LNode {
    	int data;
    	struct LNode *next;
    } *LinkList;
    
    //初始化
    void init(LinkList &L) {
    	L = NULL;
    }
    
    //头插
    void head_insert(LinkList &L, int x) {
    	LinkList newP = (LinkList)malloc(sizeof(LNode));
    	newP->data = x;
    	
    	newP->next = L;
    	L = newP;
    }
    
    //按位序查找
    LinkList get(LinkList L, int k) {
    	if (k < 1) {
    		printf("查找位置非法!");
    		return NULL;
    	}
    	int i = 1;
    	if (L != NULL && i <= k) {
    		L = L->next;
    		i++;
    	}
    	if (i == k) {
    		return L;
    	}
    	printf("查找位置非法!");
    	return NULL;
    }
    
    //遍历输出
    void print(LinkList L) {
    	printf("\n");
    	while (L) {
    		printf("%4d ", L->data);
    		L = L->next;
    	}
    	printf("\n");
    }
    
    
    int main() {
    	LinkList L;
    	init(L);
    	head_insert(L, 15);
    	head_insert(L, 25);
    	head_insert(L, 35);
    	print(L);
    	printf("\n%4d \n", get(L, 2)->data);
    	return 0;
    }
    



    带头结点的操作

    代码⑤

    #include <stdio.h>
    #include <malloc.h>
    
    //结构体
    typedef struct LNode {
    	int data;
    	struct LNode *next;
    } *LinkList;
    
    //初始化
    void init(LinkList &L) {
    	LinkList newp = (LinkList)malloc(sizeof(LNode));
    	newp->next = NULL;
    	L = newp;
    }
    
    //头插
    void head_insert(LinkList L, int x) {
    	LinkList newp = (LinkList)malloc(sizeof(LNode));
    	newp->data = x;
    
    	newp->next = L->next;
    	L->next = newp;
    }
    
    //按位序查找
    LinkList get(LinkList L, int k) {
    	if (k < 1) {
    		printf("查找位置非法!");
    		return NULL;
    	}
    	int i = 1;
    	LinkList p = L->next;
    	if (p != NULL && i <= k) {
    		p = p->next;
    		i++;
    	}
    	if (i == k) {
    		return p;
    	}
    	printf("查找位置非法!");
    	return NULL;
    }
    
    
    //遍历输出
    void print(LinkList L) {
    	printf("\n");
    	LinkList p = L->next;
    	while (p) {
    		printf("%4d ", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    
    int main() {
    	LinkList L;
    	init(L);
    	head_insert(L, 15);
    	head_insert(L, 25);
    	head_insert(L, 35);
    	print(L);
    	printf("\n%4d \n", get(L, 2)->data);
    	return 0;
    }
    
    展开全文
  • 实现单链表及其一些基本操作函数(不带头结点) 1.头文件包含 2.宏定义及节点类型描述 3.初始化、判断是否为空 4.指定位置插入操作 5.在p节点后插入元素e 6.在p节点前插入元素e 7.删除操作:删除第i节点,...
  • 结点一个结构体变量,使用这个变量的next域来记录第一个存储数据的结点的地址,头结点的data域可以使用联合体的方式记录链表的长度。 1.2各个操作方法的定义不同 如果是头指针实现,则方法中国接受这个链表的...

    1、头结点和头指针的区别

    1.1区别:
    头指针表明了链表的结点,可以唯一确定一个单链表。
    头指针指向链表的第一个结点,其记录第一个存储数据的结点的地址。
    头结点是点链表的第一个结点,若单链表有头结点,则头指针指向头结点;若单链表没有头结点,则指针指向第一个结点。
    一个单链表可有没有头结点,但不能没有头指针。
    头结点的数据域可以不存储任何数据。

    1.2记录链表的类型不同:
    头指针是一个4字节的指针,记录第一个存储数据的结点的地址。
    头结点是一个结构体变量,使用这个变量的next域来记录第一个存储数据的结点的地址,头结点的data域可以使用联合体的方式记录链表的长度。

    1.3各个操作方法的定义不同
    如果是头指针实现,则方法中国接受这个链表的类型必须是二级指针。
    头指针实现使用一级指针就OK。
    在这里插入图片描述

    2、头结点单链表

    链表和顺序表的区别:
    (1)链表在逻辑存储上是连续的,在物理存储上是不连续的。
    (2)单链表属于链表中的一种,每一个存储数据的节点除了存储数据本身之外,还要存储其直接后继结点的地址。
    在这里插入图片描述
    例:32位系统存储10个整形(int 4个字节)数据:
    顺序表存储 :总共需要堆区空间:40个字节
    单链表存储: 总共需要堆区空间:80个字节

    单链表的实现

    头结点:
    在这里插入图片描述
    头指针——在实现代码中会使用二级指针
    在这里插入图片描述
    方法的声明:

    #include<stdio.h>
    typedef int DataType;
    
    typedef struct Node
    {
    	//数据类型
    	union//结合体、联合体
    	{
    		DataType data;//存储元素
    		int length;//存储元素个数
    	};
    	//结点指针类型
    	struct Node *next; 
    }LinkList;
    
    //初始化
    void InitLinkList(LinkList *head);
    
    //销毁
    void DestroyLinkList(LinkList *head);
    
    //按位置插入插入
    bool InsertPos(LinkList *head,DataType value,int pos);
    
    //头插
    bool InsertFront(LinkList *head,DataType value);
    
    //尾插
    bool InsertRear(LinkList *head,DataType value);
    
    //按位置删除
    bool DeletePos(LinkList *head,int pos);
    
    //头删
    bool DeleteFront(LinkList *head);
    
    //尾删
    bool DeleteRear(LinkList *head);
    
    //按值删除
    bool DeleteValue(LinkList *head,DataType value);
    
    //判空
    bool IsEmpty(LinkList *head);
    
    //求长度
    int GetLength(LinkList *head);
    
    //输出
    bool PrintLinkList(LinkList *head);
    
    
    

    方法的实现:

    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include<string.h>
    #include"head.h"
    
    static LinkList *ApplyNode(DataType value,LinkList *point )
    {
           LinkList *new_node=(LinkList *)malloc(sizeof(LinkList));
           if(new_node==NULL) return NULL;
           new_node->data=value;
           new_node->next=point;
        
        return new_node;
    }
    
    void InitLinkList(LinkList *head)
    {
    	 
         if(head==NULL) exit(0);
         
    	
        head->length=0;
         head->next=NULL;
    }
    
    
    
    
    int GetLength(LinkList *head)
    {
        if(head==NULL) exit(0);
        return head->length;
    }
    
    bool InsertPos(LinkList *head,DataType value,int pos)
    {
         if(head==NULL) exit(0);
         if(pos<0||pos>GetLength(head)) return false;
         
         LinkList *p=head;
         while(pos)
        {
              p=p->next;
              pos--;
             
        }
        LinkList *new_node=ApplyNode(value,p->next);//生成新的结点
        if(new_node==NULL) return false;
               
        p->next=new_node;
        head->length++;
        return true;
         
    }
    
    bool InsertFront(LinkList *head,DataType value)
    {
         if(head==NULL) exit(0);
         LinkList *new_node=ApplyNode(value,head->next);
         if(new_node==NULL) return false;
          
         head->next=new_node;
         head->length++;
         return true;
    }
    
    bool InsertRear(LinkList *head,DataType value)
    {
         if(head==NULL) exit(0);
        return InsertPos(head,value,GetLength(head));
    }
    
    bool DeletePos(LinkList *head,int pos)
    {
         if(head==NULL) exit(0);
         if(pos<0||pos>=head->length) return false;
         LinkList *p=head;
         while(pos)
         {
            p=p->next;
            pos--;
         }
         LinkList *q=p->next;
         p->next=q->next;
         free(q);
         head->length--;
         return true;
    }
    
    bool DeleteFront(LinkList *head)
    {
         if(head==NULL) exit(0);
         return DeletePos(head,0);
    }
    
    bool DeleteRear(LinkList *head)
    {
         if(head==NULL) exit(0);
         return DeletePos(head,GetLength(head)-1);
    }
    
    bool DeleteValue(LinkList *head,DataType value)
    {
         if(head==NULL) exit(0);
         LinkList *p=head;
         LinkList *q=p->next;
         while(q!=NULL)
        {
           if(q->data==value)
            {
                p->next=q->next;
                free(q);
                q=p->next;
                head->length--;
            }
            else
            {
                p=q;
                q=q->next;
            }
        }
        return true;
    }
    
    bool IsEmpty(LinkList *head)
    { 
         if(head==NULL) exit(0);
         return head->length==0;
    }
    
    bool PointLinkList(LinkList *head)
    {
         if (head == NULL) exit(0);
    
    	LinkList *p = head->next;
    
    	while (p != NULL)
    	{
    		printf("%d  ", p->data);
    		p = p->next;
    	}
    
    	printf("\n");
    }
    void DestroyLinkList(LinkList *head)
    {
         if(head=NULL) exit(0);
         while(IsEmpty(head)!=NULL)
    	 {
          DeleteFront(head);
    
    	 }
    }
    
    //找到第K个结点
    LinkList *FindK(LinkList *head, int k)  //  0< k <= length
    {
    	if (head == NULL)  return NULL;
    
    	if (k <= 0 || k > head->length)  return NULL;
    
    	int pos = head->length - k + 1;
    
    	LinkList *p = head;
    
    	while (pos)
    	{
    		p = p->next;
    		pos--;
    	}
    	
    	return p;
    }
    
    //  不能直接获得length的情况
    LinkList *FindOfK2(LinkList *head, int k)
    {
    	if (head == NULL)  return NULL;
    
    	if (k <= 0)  return NULL;
    
    	LinkList *p = head;
    
    	while (k && p != NULL)
    	{
    		p = p->next;
    		k--;
    	}
    
    	if (p == NULL)  return NULL;
    
    	LinkList *q = head;
    	while (p != NULL)
    	{
    		p = p->next;
    		q = q->next;
    	}
    
    	return q;
    }
    
    //O(1)删除非尾结点p
    bool DeletePos1(LinkList *head,int pos)
    {
        if(head==NULL) return false;
        if(pos<0||pos>=head->length) return false;
        LinkList *p=head;
        while(pos)
        {
            p=p->next;
            pos--;
        }
        LinkList *q=p->next;
        p->next=q->next;
        free(q);
        head->length--;
        return true;
        
    }
    
    //将单链表逆置  -- 结点逆置
    void Reverse(LinkList *head)
    {
        if(head==NULL) return;
        LinkList *p=NULL;
        LinkList *q=head->next;
        LinkList *s=q->next;
    	
        while(q!=NULL)
        {
            q->next=p;
            p=q;
            q=s;
            if(s!=NULL) s=s->next;
        }
        head->next=p;
    }
    //判断两个结点是否相交,返回相交的第一个结点
    LinkList *IsIntersect(LinkList *head1,LinkList *head2)
    {
        if(head1==NULL||head2==NULL) return false;
        LinkList *p=head1;
        LinkList *q=head2;
        if(head1->length>head2->length)
        {
            for(int i=0;i<head1->length-head2->length;i++)
            {
                p=p->next;
            }
        }
        else
        {
            for(int i=0;i<head2->length-head1->length;i++)
            {
                q=q->next;
            }
        }
        while(p!=q)
        {
            p=p->next;
            q=q->next;
        }
    	
        return p;
    }
    
    LinkList *IsIntersect2(LinkList *head1, LinkList *head2)
    {
    	if (head1 == NULL || head2 == NULL)  return NULL;
    
    	LinkList *p = head1;
    	LinkList *q = head2;
    
    	while (p != q)
    	{
    		if (p != NULL) p = p->next;
    		else  p = head2;
    		if (q != NULL) q = q->next;
    		else q = head1;
    // 		p = p != NULL ? p->next : head2;
    // 		q = q != NULL ? q->next : head1;
    	}
    
    	return p;
    }
    //判断单链表是否有环,如果有,返回入环的第一个结点
    LinkList *IsLoop(LinkList *head)
    {
        if(head==NULL) return NULL;
        LinkList *fast=head;
        LinkList *slow=head;
        while(fast!=NULL&&fast->next!=NULL)
        {
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow) break;
        }
        LinkList *p=fast;
        LinkList *q=slow;
        while(q!=p)
        {
            p=p->next;
            q=q->next;
        }
        return p;
    }
    
    int main()
    {
    	LinkList list;
    	InitLinkList(&list);
    	InsertFront(&list,1);
    	InsertPos(&list,2,1);
    	InsertRear (&list,3);
    	InsertRear (&list,4);
    	InsertRear (&list,5);
    	DeletePos(&list,1);
    	printf("单链表长度为:%d\n",GetLength(&list));
    	printf("第一次输出:");
    	PointLinkList(&list);
    	DeleteValue(&list,4);
    	InsertPos(&list,2,1);
    	printf("第二次输出:");
    	PointLinkList(&list);
    	return 0;
    }
    
    

    3、头指针单链表

    在这里插入图片描述
    方法的声明:

    #include<stdio.h>
    typedef  int  DataType;
    
    typedef struct Node
    {
      	DataType    data;    //   记录本结点存储的数据
        struct Node  *next;  //   记录下一个结点的地址
    }LinkList;
    
    // 初始化
    void  InitLinkList(LinkList **phead);
    //  插入
    bool InsertLinkList(LinkList **phead, DataType value, int pos);
    
    bool InsertLinkListHead(LinkList **phead, DataType value);
    
    bool InsertLinkListRear(LinkList **phead, DataType value);
    
    //  删除
    bool DeleteLinkList(LinkList **phead, int pos);
    
    bool DeleteLinkListHead(LinkList **phead);
    
    bool DeleteLinkListRear(LinkList **phead);
    
    //  长度
    int GetLength(LinkList **phead);
    //  判空
    bool  Empty(LinkList **phead);
    //  销毁
    void  DestroyLinkList(LinkList **phead);
    
    //  显示
    void  ShowLinkList(LinkList **phead);
    

    方法的实现:

    #include "head.h"
    #include <string.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <malloc.h>
    
    
    static LinkList *ApplyNewNode(DataType value, LinkList *next)
    {
    	LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));
    	if (new_node == NULL)  exit(0);
    
    	new_node->data = value;
    	new_node->next = next;
    
    	return new_node;
    }
    
    
    void  InitLinkList(LinkList **phead)  //  phead中存储的值就是main方法中的phead变量的地址
    {
    	if (phead == NULL)  exit(0);
    
    	*phead = NULL;
    }
    
    int GetLength(LinkList **phead)
    {
    	if (phead == NULL)  exit(0);
    
    	int length = 0;
    
    	LinkList *p = *phead;
    
    	while (p != NULL)
    	{
    		length++;
    		p = p->next;
    	}
    
    	return length;
    }
    
    bool InsertLinkList(LinkList **phead, DataType value, int pos)
    {
    	if (phead == NULL)  exit(0);
    
    	if (pos < 0 || pos > GetLength(phead))  return false;
    
    	//  在头指针的后面插入新结点,头插法必须特殊处理: 因为只有在这需要修改头指针的值
    	if (pos == 0)  return InsertLinkListHead(phead, value);//  头插
    
    
    	LinkList *p = *phead;
    
    	while (pos > 1)
    	{
    		p = p->next;
    		pos--;
    	}
    
    	//  while循环结束后,就需要在p所指向的结点的后面插入新结点
    
    	/* 
    		LinkList *new_node = ApplyNewNode(value, p->next); 
    		p->next = new_node;
    	*/
    	p->next = ApplyNewNode(value, p->next);
    	return true;
    }
    
    bool InsertLinkListHead(LinkList **phead, DataType value)
    {
    	if (phead == NULL)  exit(0);
    
    	*phead = ApplyNewNode(value, *phead);
    
    	return true;
    }
    
    bool InsertLinkListRear(LinkList **phead, DataType value)
    {
    	if (phead == NULL)  exit(0);
    
    	//  链表本身是空的,尾插相当于头插
    	if (Empty(phead))  return InsertLinkListHead(phead, value);
    
    	LinkList *p = *phead;
    
    	while (p->next != NULL)  p = p->next;  //  while循环结束后,p就是最后一个结点
    
    	p->next = ApplyNewNode(value, NULL);
    	return true;
    }
    
    bool  Empty(LinkList **phead)
    {
    	if (phead == NULL)  exit(0);
    
    	if (*phead == NULL)  return true;
    
    	return false;
    }
    
    
    
    bool DeleteLinkList(LinkList **phead, int pos)
    {
    	if (phead == NULL)  exit(0);
    
    	if (pos < 0 || pos >= GetLength(phead))  return false;
    
    	if (pos == 0)  return DeleteLinkListHead(phead);
    
    	LinkList *p = *phead;  //  p指向的是第一个数据结点
    
    	while (pos > 1)
    	{
    		p = p->next;
    		pos--;
    	}
    
    	//  while循环结束后,要删除的结点时p->next
    	LinkList *q = p->next;
    	p->next = q->next;
    	free(q);
    	return true;
    }
    
    bool DeleteLinkListHead(LinkList **phead)
    {
    	if (phead == NULL)  exit(0);
    
    	if (Empty(phead))  return false;
    
    	LinkList *p = *phead;
    
    	*phead = p->next;
    	free(p);
    	return true;
    }
    
    bool DeleteLinkListRear(LinkList **phead)
    {
    	if (phead == NULL)  exit(0);
    
    	if (Empty(phead))  return false;
    
    	LinkList *front = NULL;
    	LinkList *p = *phead;
    
    	while (p->next != NULL)
    	{
    		front = p;
    		p = p->next;
    	}
    
    	if (front == NULL)  return DeleteLinkListHead(phead);
    
    	front->next = NULL;
    	free(p);
    	return true;
    }
    
    void  DestroyLinkList(LinkList **phead)
    {
    	if (phead == NULL)  exit(0);
    
    	while (!Empty(phead))
    	{
    		DeleteLinkListHead(phead);
    	}
    }
    
    void  ShowLinkList(LinkList **phead)
    {
    	if (phead == NULL)  exit(0);
    
    	LinkList *p = *phead;
    
    	while (p != NULL)
    	{
    		printf("%d  ", p->data);
    		p = p->next;
    	}
    
    	printf("\n");
    }
    
    int main()
    {
    	LinkList *list;
    	InitLinkList(&list);
    	InsertLinkListHead(&list,6);
    	InsertLinkListHead(&list,5);
    	InsertLinkListHead(&list,4);
    	InsertLinkListHead(&list,3);
    	InsertLinkListHead(&list,2);
    	InsertLinkListHead(&list,1);
    	DeleteLinkList (&list,5);
    	printf("第一次输出:");
    	ShowLinkList(&list);
    	InsertLinkList(&list,6,5);
    	InsertLinkListRear(&list,7);
    	DeleteLinkListHead(&list);
    	DeleteLinkListRear(&list);
    	printf("第一次输出:");
    	ShowLinkList(&list);
    
    
    	return 0;
    }
    

    头指针单链表操作时的转化

    因为头结点实现的单链表相比于头指针实现的单链表,操作时特殊情况少一些。在实现一些有指针的单链表的操作时,可以虚拟构建出一个头结点。

    bool Funaction(LinkList **phead)
    {
    	//虚拟出来的头结点
    	LinkList *head=(LinkList *)malloc(sizeof(LinkList));
    	head->next =*phead;
    
    	LinkList *p=head;//p指向头结点
    	LinkList *q=p->next;
    
    	while(q->next!=NULL)
    	{
    		p=q;
    		q=q->next;
    	}
    
    	p->next=q->next ;
    	free(q);
    	*phead=head->next;
    	free(head);
    }
    
    
    展开全文
  • c代码-不带头结点单链表创建——头插法
  • 对于不带头结点单链表 L,设计一个递归算法逆序输出所有结点值 #include "LinkList.cpp" #include <bits/stdc++.h> void Revdisp(LinkNode *L) { // 逆序输出 if(L == NULL) return ; else{...
    #include "LinkList.cpp"
    #include <bits/stdc++.h>
    
    void Revdisp(LinkNode *L) {  // 逆序输出 
    	
    	if(L == NULL)
    		return ;
    	else{
    		Revdisp(L->next);
    		cout <<" " << L->data;
    	}
    
    }
    
    int main() {
    	int a[] = {1,2,5,2,3,2};
    	LinkNode *L,*p;
    	int n = sizeof(a) / sizeof(a[0]);
    	L = CreateList(a,n);
    	DispList(L);
    	cout << endl;
    	Revdisp(L);
    	Release(L);
    	return 0;
    }
    
    #include<bits/stdc++.h>
    
    using namespace std;
    
    typedef struct Node {
    	int data;
    	struct Node *next;
    } LinkNode;
    
    LinkNode *CreateList(int a[],int n) {
    	if(n < 0)
    		return NULL;
    	LinkNode *head = (LinkNode *)malloc(sizeof(LinkNode));
    	LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    	p = head;
    	head->data = a[0];
    	int i = 0;
    	for(i = 1; i < n; i++) {
    	
    		LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
    		node->data = a[i];
    		p->next = node;
    		p = node;
    	}
    	p->next = NULL;  // 尾结点next域置为空
    	return head;
    }
    
    void DispList(LinkNode *ln) {
    	cout << " "; 
    	if(ln != NULL){
    		cout << ln->data;
    		DispList(ln->next);
    	}
    }
    
    void Release(LinkNode *ln) {
    	if(ln->next == NULL)
    		return ;
    	else {
    		Release(ln->next);
    		free(ln);
    	}
    }
    
    展开全文
  • 编写不带头结点单链表的建立、插入和删除操作算法。 一、问题描述 编写一个不带头节点的单链表 二、基本要求 1) 建立 2) 插入 3) 删除 三、算法思想 选用不带头结点的单链表,在第一个元素节点前插入节点时...
  • 利用c++实现不带头结点链表的基本操作实现,如逆序建立链表,插入、删除链表元素等。
  • //计算结点个数 while (p != NULL) { n++; p = p->next; } if (k > n) { return; } p = L; while (n > k) { p = p->next; n--; } printf("%d,\n", p->val); } 2. 递归遍历 缺点:找到结点数据还要继续遍历,直到...
  • 对于不带头结点单链表 L,设计一个递归算法删除第一个值为 x 的结点 #include "LinkList.cpp" #include <bits/stdc++.h> void Delfirstx(LinkNode *&L,int x) { // 删除第一个值为 x 的结点 if ...
  • 不带头结点单链表

    2021-11-18 22:03:16
    因为不带头结点,无需初始化,最后返回head 尾插法 如果是第一个结点,则需让head指向这个结点,再利用另一指针r保存head,并用r进行之后的节点插入。除第一个结点外其他结点的插入与带头结点的单链表一致。 Li
  • //不带头结点单链表 #include<stdio.h> #include<stdlib.h> #define LEN sizeof(LNode) typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; //初始化一个空的单链表 bool...
  • 不带头结点单链表java实现分析:我们先说带头结点的单链表,带头结点的单链表在初始化时产生一个head结点,其data域和next域均为空。对带头结点的单链表进行操作分为头部操作和尾部操作。1.头部操作:**插入:**...
  • 利用 KMP 算法求子串在主串中出现的次数.c
  • 不带头结点单链表操作,包括插入、遍历、统计结点数等,要求写出数据结构算法思想及C语言实现函数 本文为博主原创文章,未经博主允许不得转载。 版权为陈博超所有,第次于2021年06月22日发表于BLOG上 本BLOG...
  • 不带头节点的单链表,包含头插尾插,及头删尾删,链表逆序
  • 结构体后的*List是一个指向结构体的指针类型,我们通过它来定义该类型的指针。如:List p ; 则这个p就是指向LinkedList结构体的一个...(所以说头指针是必然存在的,但单链表不一定有头结点,注意区分头指针和头结点
  • (1)pre=NULL,s=NULL,p//链表为空或链表不止一个节点 (2)s=p;//s下移 (3)p=p->next; //p下移 (5) s->next=pre;//s的下一位为自己(s)的上一位,即ai指向ai+1 (4)pre=s;//pre指向s,...
  • 带头结点单链表就地逆置算法

    千次阅读 2021-09-17 15:54:28
    1、带头结点单链表就地逆置算法 部分函数调用参考如下:https://blog.csdn.net/qq_50504109/article/details/120288749 /** * 单向链表的逆置,说白了就是头插法的利用,只不过我们这次插入的数据,不是自己决定的...
  • 用c语言实现对带有头节点和不带头结点单链表进行建立、插入和删除的操作
  • 不带头结点单链表的实现(C语言)不带头结点单链表的实现(C语言)链表中的数据是以结点来表示的,每结点的构成:元素(数据元素的映象) +指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每...
  • 2022.3.17 不带头结点单链表

    千次阅读 2022-03-17 09:34:33
    1. 不带头结点单链表如下图 2. 结构体设计 no_head_list.h文件 #pragma once //防止头文件重复 typedef int ELEM_TYPE; typedef struct Node { ELEM_TYPE data;//数据域(1.头结点:不保存任何数据 2....
  • typedef struct node { struct node * next ; int data ; } * LinkList , NODE ; LinkList reverseList ( LinkList head ) if ( head == NULL ...//返回新的第一个结点 }
  • 数据结构--带头结点单链表

    千次阅读 2022-02-28 22:14:01
    单链表分为:带头结点和不带头结点不带头结点单链表需要用到二级指针,容易出错。
  • 单链表不带头结点

    千次阅读 2022-02-19 13:17:40
    单链表不带头结点结构体设计: //不带头结点的结构体设计: typedef int ELEM_TYPE; //有效数据节点结构体设计 typedef struct Node { ELEM_TYPE data;//数据域 (1.头结点:不保存任何数据 2.有效数据节点:...
  • p3指向后面的一个结点,p3主要作用是当p2指向改变之后,p2结点的后面的结点如果不用一个指针指向的话,就找到了。 代码: void Reserve(ListNode*& head) { if (head == NULL || head->next == NULL) ...
  • 不带头结点 //不带头结点 void Reverse(SLink *&L){ //用指针p遍历,r为p的后继 SLink *p,*r; p=L; r=p->next; L->next=NULL; //遍历链表 while(p!=NULL){ p=r;//向后遍历 r=p->next; p->next=L;//实现逆置...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,113
精华内容 6,445
热门标签
关键字:

对于一个不带头节点的单链表