精华内容
下载资源
问答
  • 主要为大家详细介绍了Java实现带头结点单链表,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 不带头结点不带头结点不带头结点! 实现单链表及其一些基本操作函数(不带头结点) 1.头文件包含 2.宏定义及节点类型描述 3.初始化、判断是否为空 4.指定位置插入操作 5.在p节点后插入元素e 6.在p节点前...
  • c代码-不带头结点单链表创建——头插法
  • 利用 KMP 算法求子串在主串中出现的次数.c
  • //LinkList 等价于 LNode* //以数组建立 不带头结点单链表,(单链表,元素个数,数组传入) LinkList CreatListByArray(LinkList &L,int n,int a[n]){ int i = 0; L = (LinkList) malloc(sizeof(LNode)); LNode ...
    //
    // Created by 焦娇 on 2021/9/17.
    //
    
    #ifndef CHAPTER2_LINELINK_LLK_H
    #define CHAPTER2_LINELINK_LLK_H
    
    #endif //CHAPTER2_LINELINK_LLK_H
    #include <iostream>
    
    using namespace std;
    typedef int Elemtype;
    typedef struct LNode {
        Elemtype data;              //数据域
        struct LNode *next;         //指针域,指向后继
    }LNode, *LinkList;              //LinkList 等价于 LNode*
    
    //以数组建立 不带头结点的单链表,(单链表,元素个数,数组传入)
    LinkList CreatListByArray(LinkList &L,int n,int a[n]){
        int i = 0;
        L = (LinkList) malloc(sizeof(LNode));
        LNode *s;
        L->next = NULL;
        LNode *r = L;
        L->data = a[0];
        for (i = 1; i < n; i++) {
            s = (LinkList) malloc(sizeof(LNode));
            s->data = a[i];
            r->next = s;
            s->next = NULL;
            r = s;
        }
    }
    //以数组建立 带头结点的单链表
    LinkList CreatLListByArray(LinkList &L,int n,int a[n]){
        int i = 0;
        L = (LinkList) malloc(sizeof(LNode));
        LNode *s;
        L->next = NULL;
        LNode *r = L;
        L->data = 0;
        for (i = 0; i < n; i++) {
            s = (LinkList) malloc(sizeof(LNode));
            s->data = a[i];
            r->next = s;
            s->next = NULL;
            r = s;
        }
    }
    //带头结点 头插法
    LinkList CreatListByHead(LinkList &L){
        LNode *s;
        int x;
        L = (LinkList)malloc(sizeof (LNode));
        L->next = NULL;
        cout<<"请输入需要创建的链表,以 9999 为结束:";
        cin>>x;
        while (x!=9999){
            s = (LinkList)malloc(sizeof (LNode));
            s->data = x;
            s->next = L->next;
            L->next = s;
    
            cin>>x;
        }
        return L;
    }
    //带头结点 尾插法
    LinkList CreatListByTail(LinkList &L){
        int x;
        L = (LinkList)malloc(sizeof (LNode));
        LNode *s;
        LNode *r = L;
        cout<<"请输入需要创建的链表,以 9999 为结束:";
        cin>>x;
    
        while (x!=9999){
            s = (LinkList)malloc(sizeof (LNode));
            s->data = x;
    
            r->next = s;
            r = s;
            cin>>x;
        }
        r->next = NULL;
        return L;
    }
    //输出不带头结点的 单链表
    void PrintLinkListwithoutL(LinkList &L){
        cout<<"单链表为:"<<endl;
        for(LinkList I = L;I!=NULL;I=I->next){
            cout<<I->data<<"->";
        }
        cout<<"Null";
    }
    //输出带头结点的 单链表
    void PrintLinkListwithL(LinkList &L){
        cout<<"单链表为:"<<endl;
        for(LinkList I = L->next;I!=NULL;I=I->next){
            cout<<I->data<<"->";
        }
        cout<<"Null";
    }
    
    展开全文
  • 数据结构(不带头结点单链表

    千次阅读 2019-11-26 10:59:57
    数据结构 单链表 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点...不带头结点单链表 头结点一般在栈区或者数据区开辟且头结点不存储...

    数据结构

    单链表

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据
    在写单链表的时候,需要对结构体有一定的了解(这里就不做过多的结构体介绍)

    不带头结点的单链表

    头结点一般在栈区或者数据区开辟且头结点不存储有效数据,但不带头结点的单链表是以一个指针来存储第一个结点的位置,相当于带头结点单链表的头结点只存储地址而不存储目前的结点个数

    一、创建不带头结点的单链表
    不带头结点的单链表通过结构体创建

    typedef int ElemType;
    
    typedef struct LNode
    {
    	ElemType  data;
    	LNode *next;
    }LNode,*LinkList;
    

    二、单链表所实现的功能(不带头结点的单链表)
    1.计算结点数

    static int GetLinkList_Length(LinkList head)       //计算结点数
    {
    	LinkList p = head;
    	int length = 0;
    	while(p!=NULL)
    	{
    		length++;
    		p = p->next;
    	}
    	return length;
    }
    

    2.找目标结点的前一个

    static LinkList FindPrior(LinkList head,int pos)       //找目标结点的前一个
    {
    	LinkList p = head;
    	while(pos-1)
    	{
    		p = p->next;
    		pos--;
    	}
    	return p;
    }
    

    3.单链表创建结点并赋值

    static LinkList ApplyNode(ElemType val,LinkList next)     //创建节点及赋值
    {
    	LinkList p = (LinkList)malloc(sizeof(LNode));
    	if(p == NULL)  return NULL;
    	p->data = val;
    	p->next = next;
    	return p;
    }
    

    4.单链表初始化

    void Init_LinkList(LinkList *head)           //初始化
    {
    	if(head == NULL) exit(0);
    	*head = NULL;
    }
    

    5.插入
    (1)位置插

    int InsertLinkList_Pos(LinkList *head,ElemType val,int pos)     //位置插
    {
    	if(head == NULL)  exit(0);
    	if(pos<0||pos>GetLinkList_Length(*head))  return false;
    	if(pos == 0)
    	{
    		if(InsertLinkList_Head(head,val))  return true;
    	}
    	LinkList p = FindPrior(*head,pos);
    	LinkList q = ApplyNode(val,p->next);
    	p->next = q;
    	return true;
    }
    

    (2)头插

    int InsertLinkList_Head(LinkList *head,ElemType val)        //头插
    {
    	assert(head!=NULL);
    	if(head == NULL)  exit(0);
    	LinkList q = ApplyNode(val,*head);
    	*head = q;
    	return true;
    }
    

    (3)尾插

    int InsertLinkList_Tail(LinkList *head,ElemType val)        //尾插
    {
    	if(head == NULL)  exit(0);
    	return InsertLinkList_Pos(head,val,GetLinkList_Length(*head));
    }
    

    6.删除
    (1)位置删

    int DeletLinkList_Pos(LinkList *head,int pos)        //位置删
    {
    	if(head == NULL)  exit(0);
    	if(pos<0||pos>=GetLinkList_Length(*head))  return false;
    	if(pos == 0)
    	{
    		return DeletLinkList_Head(head);
    	}
    	LinkList p = FindPrior(*head,pos);
    	LinkList q = p->next;
    	p->next = q->next;
    	free(q);
    	return true;
    }
    

    (2)头删

    int DeletLinkList_Head(LinkList *head)        //头删
    {
    	if(head == NULL||*head == NULL)  return false;
    	LinkList p = *head;
    	*head = p->next;
    	free(p);
    	return true;
    }
    

    (3)尾删

    int DeletLinkList_Tail(LinkList *head)       //尾删
    {
    	if(head == NULL)  exit(0);
    	return DeletLinkList_Pos(head,GetLinkList_Length(*head)-1);
    }
    

    7.打印

    void Show_LinkList(LinkList head)        //打印
    {
    	if(head == NULL)  return ;
    	LinkList p = head;
    	while(p!=NULL)
    	{
    		printf("%d  ",p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    

    8.清空单链表

    int Clear_LinkList(LinkList *head)       //清空
    {
    	if(head == NULL)  return true;
    	while(*head != NULL)
    	{
    		DeletLinkList_Head(head);
    	}
    	return true;
    }
    

    9.销毁单链表

    int Destroy_LinkList(LinkList *head)          //销毁
    {
    	if(head == NULL)  return false;
    	return Clear_LinkList(head);
    }
    

    总代码:

    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    typedef int ElemType;
    
    typedef struct LNode
    {
    	ElemType  data;
    	LNode *next;
    }LNode,*LinkList;
    
    static int GetLinkList_Length(LinkList head)       //计算结点数
    {
    	LinkList p = head;
    	int length = 0;
    	while(p!=NULL)
    	{
    		length++;
    		p = p->next;
    	}
    	return length;
    }
    
    static LinkList ApplyNode(ElemType val,LinkList next)     //创建节点及赋值
    {
    	LinkList p = (LinkList)malloc(sizeof(LNode));
    	if(p == NULL)  return NULL;
    	p->data = val;
    	p->next = next;
    	return p;
    }
    
    static LinkList FindPrior(LinkList head,int pos)       //找目标结点的前一个
    {
    	LinkList p = head;
    	while(pos-1)
    	{
    		p = p->next;
    		pos--;
    	}
    	return p;
    }
    
    void Init_LinkList(LinkList *head)           //初始化
    {
    	if(head == NULL) exit(0);
    	*head = NULL;
    }
    
    int InsertLinkList_Head(LinkList *head,ElemType val)        //头插
    {
    	assert(head!=NULL);
    	if(head == NULL)  exit(0);
    	LinkList q = ApplyNode(val,*head);
    	*head = q;
    	return true;
    }
    
    int InsertLinkList_Pos(LinkList *head,ElemType val,int pos)     //位置插
    {
    	if(head == NULL)  exit(0);
    	if(pos<0||pos>GetLinkList_Length(*head))  return false;
    	if(pos == 0)
    	{
    		if(InsertLinkList_Head(head,val))  return true;
    	}
    	LinkList p = FindPrior(*head,pos);
    	LinkList q = ApplyNode(val,p->next);
    	p->next = q;
    	return true;
    }
    
    int InsertLinkList_Tail(LinkList *head,ElemType val)        //尾插
    {
    	if(head == NULL)  exit(0);
    	return InsertLinkList_Pos(head,val,GetLinkList_Length(*head));
    }
    
    
    int DeletLinkList_Head(LinkList *head)        //头删
    {
    	if(head == NULL||*head == NULL)  return false;
    	LinkList p = *head;
    	*head = p->next;
    	free(p);
    	return true;
    }
    
    int DeletLinkList_Pos(LinkList *head,int pos)        //位置删
    {
    	if(head == NULL)  exit(0);
    	if(pos<0||pos>=GetLinkList_Length(*head))  return false;
    	if(pos == 0)
    	{
    		return DeletLinkList_Head(head);
    	}
    	LinkList p = FindPrior(*head,pos);
    	LinkList q = p->next;
    	p->next = q->next;
    	free(q);
    	return true;
    }
    
    int DeletLinkList_Tail(LinkList *head)       //尾删
    {
    	if(head == NULL)  exit(0);
    	return DeletLinkList_Pos(head,GetLinkList_Length(*head)-1);
    }
    
    int Clear_LinkList(LinkList *head)       //清空
    {
    	if(head == NULL)  return true;
    	while(*head != NULL)
    	{
    		DeletLinkList_Head(head);
    	}
    	return true;
    }
    
    int Destroy_LinkList(LinkList *head)          //销毁
    {
    	if(head == NULL)  return false;
    	return Clear_LinkList(head);
    }
    
    void Show_LinkList(LinkList head)        //打印
    {
    	if(head == NULL)  return ;
    	LinkList p = head;
    	while(p!=NULL)
    	{
    		printf("%d  ",p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    int main()
    {
    	//以下为测试内容
    	LinkList list;
    	Init_LinkList(&list);
    	for(int i=0;i<10;i++)
    	{
    		InsertLinkList_Head(&list,i);
    	}
    	InsertLinkList_Pos(&list,200,0);
    	InsertLinkList_Tail(&list,100);
    	Show_LinkList(list);
    
    	DeletLinkList_Head(&list);
    	DeletLinkList_Tail(&list);
    	DeletLinkList_Pos(&list,9);
    	Show_LinkList(list);
    
    	//Clear_LinkList(&list);
    	Destroy_LinkList(&list);
    	Show_LinkList(list);
    	return 0;
    }
    
    展开全文
  • 不带头结点单链表

    2021-05-03 10:51:57
    为了建立元素间的线性关系,每个节点除了存放自身的信息外,还要存放一个指向下一个结点的指针。其结构图如下 | data| next| 结点类型定义代码如下 typedef struct{ //定义单链表结点类型 ElemType data; //数据...

    不带头结点的单链表

    定义

     线性表的链式存储又称单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立元素间的线性关系,每个节点除了存放自身的信息外,还要存放一个指向下一个结点的指针。其结构图如下  
               | data| next|
    结点类型定义代码如下
    
    typedef struct{         //定义单链表结点类型
    ElemType data;          //数据域
    struct LNode *next;     //指针域
              }LNode,*LinkList;   
       //LNode:struct类型的别名,LNode*LinkList:指向链表的指针,相当于struct LNode *LinkList;
    

    初始化

    void InitList(LinkList *L){ 
     // 创建链表时要将改变值传回main函数,所以用引用类型的参数
         *L = NULL;
    
    }
    调用InitList(&head);
    方式二:
    void InitList(LNode *head){
        head=NULL;
    }
    
    

    判断是否是空表

    bool Empty(LinkList L) //判断链表是否为空 
    {
    	return (L==NULL);
    }
    

    求表长

    int GetLength(LinkList L) 
    {	
        int len = 0; 
    	if(L == NULL){
    		printf("空表");
    		return len;
    	 }
    	 LNode *p= &L;
    	 while(p != NULL){
    		p = p->next;
    		len++;
    	}      
    	return len;
    }
    

    打印表

    void PrintList(LinkList L)
    {  
       if(L==NULL) return;
       LNode *p = L;
       while(p){
       printf("%d-->",p->data);
       p = p->next;
       }
       printf("NULL\n");
    }
    

    查找

    按位查找结点

    LNode *GetElem(LinkList L,int i){
    	if(i == 1) return L;
    	if(i < 1) return NULL; 
    	int j = 0;
    	LNode *p = L;
    	while(p != NULL&& j<i){
    		p = p->next;
    		j++;
    	} 
    	return p;
    }
    

    按值查找结点

    LNode *GetElem(LinkList L,int e){
    	LNode *p =  L;
    	while(p && p->data != e)
    	p =p->next;
    	return p;
    } 
    

    插入

    指定结点的后插操作

    //指定结点的后插操作 
    bool InsertNextNode(LNode *p,int e){
    	if(p == NULL){
    		return false;
    	} 
    	LNode *s = malloc(sizeof(LNode));
    	if(s == NULL) {
    		return false; //分配空间失败 
    	}
    	s->data = e;
    	s->next = p->next;
    	p->next = s;
    	return true; 
    }
    

    在给定结点前插入

    将要插入的节点的数据与指定结点的数据交换,然后将这个新节点接在给定结点后

    bool InsertPrioNode(LNode *p,int e){
    	if(p==NULL){
    		return false;
    	}
    	LNode *s = malloc(sizeof(LNode));
    	s->data = p->data;
    	p->data = e;
    	s->next = p->next;
    	p->next = s;
    	return true;
    }
    

    按位序插入

    bool ListInsert(LinkList *L,int i,int e){
    	//*L表示指向第一个结点的 L的指针 
    	if(i<1){
    		return false;
    	}
    	if(i == 1)
    	{
    		LNode *s = malloc(sizeof(LNode));
    		s->data = e;
    		s->next = *L;
    		*L = s;
    		return true;
    	}
    	
    	LNode *p = GetElem(*L,i - 1); //获取前一个结点
    	InsertNextNode(p,e); 
    	return true;
    } 
    

    创表

    头插法

    void CreateListH(LinkList *L){
       LNode *t;         
         int a,n,i=0;
         printf("请输入表长:");
         scanf("%d",&n);
         while(i < a){
         	scanf("%d",&a);
         	t=(LNode *)malloc(sizeof(LNode));
            t->data=a;
            t->next=*L;
            *L = t;
    		 i++;
         }
    } 
    

    尾插法

    void CreatListT(LinkList *L){
         LNode *p,*t;         /*p工作指针,t临时指针*/
         int a,i=1;
         while(scanf("%d",&a)){
              if(a!=0){
                   t=(LNode *)malloc(sizeof(LNode));
                   t->data=a;
                   if(i==1){
                        *L=t;   
                   }
                   else{
                        p->next=t;
                   }
                   p=t;
    }
              else{   
                   p->next=NULL;
                   break;   
              }
              i++;
         }
    }
    

    删除

    删除给定结点

    bool DeleteList(LNode *p){
    	if(p==NULL) return false;
    	LNode *q = p->next;
    	p->data = q->data;
    	p->next = q->next;
    	free(q);
    	return true;
    } 
    

    按序位删除

    bool DeleteList(LinkList *L,int i,int *e){
    	LNode *p = GetElem(*L,i);
    	  DeleteList(p);
    	  return true;
    }
    

    销毁表

    void DestoryLinklist(LinkList *L){
      //摧毁链表 
        LinkList cur = *L;
        LinkList pre = NULL;
        if (*L == NULL){
            printf("链表为空");
            return ;
        }
        if (cur->next = NULL){
            *L = NULL;
            free(cur);
            cur = NULL;
            return ;
        }
        while(cur){
            pre = cur;
            cur = cur->next;
            free(pre);
            pre = NULL;
        }
    } 
    

    总结:不带头结点的遍历,增加结点等操作的循环判断条件都是 L != NULL,增删结点,创建链表,初始化等操作都需要用到函数值传递,所以函数的参数都用指针

    展开全文
  • 给定一个不带头结点单链表,写出将链表倒置的算法
  • 带头结点单链表

    2021-04-20 15:00:21
    带头结点单链表定义操作初始化结点前插后插查找插入删除求表长 定义 线性表的链式存储方式称为单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素。 为了实现数据元素之间的线性关系,所以每个结点中...

    定义

    线性表的链式存储方式称为单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素。

    为了实现数据元素之间的线性关系,所以每个结点中除了存储自身的值以外,还会存放一个指向后继的指针。

    具体的代码如下:

    typedef struct LNode{
    	int data;//结点的数据
    	LNode* Next;//指向下一结点的指针
    }LNode,*LinkList;//前者为结点,后者为链表(只是两种不同表述方式)
    

    操作

    在单链表的具体实现中,有两种实现方式,一种是带头结点的单链表,一种是不带头结点的单链表。

    两者的共同点在于,都有一个头指针用于指向链表的第一个结点。

    两者的区别在于,带头结点的单链表会有一个头结点,这个头结点的Next指针指向单链表的第一个结点,所以头指针是指向头结点的;而不带头结点的单链表则是由头指针直接指向第一个结点。

    因为带头结点的单链表在代码实现的时候更加简便,所以本文以带头结点的形式来实现单链表各种操作。

    初始化

    bool InitList(LinkList& L)
    {
    	L = (LNode*)malloc(sizeof(LNode));//创建头结点
    	if (L == NULL)
    	{
    		cout << "内存不足分配失败!" << endl;
    		return false;
    	}
    	else
    	{
    		L->next = NULL;//初始化的链表中没有结点,所以指向NULL
    		return true;
    	}
    }
    

    在初始化时,要注意使用malloc函数的判空,因为使用malloc时可能会出现失败的情况,加入判空可以增加代码的健壮性。

    结点前插

    给定链表的一个结点,实现在此结点的前面插入一个结点,有两种实现方式。
    第一,从头开始找到该结点的前驱结点实现插入(这种实现方式需要我们知道头指针,并且时间复杂度为O(n))
    第二,原地前插

    bool InsertPriorNode(LNode* p, int e) {//在p结点前面插入元素e
    	if (p == NULL) {//判断p结点是否为空,如果为空是不能前插的
    		return false;
    	}
    	LNode* L = (LNode*)malloc(sizeof(LNode));
    	if (L == NULL) {
    		cout << "内存分配失败" << endl;
    		return false;
    	}
    	else {
    		L->next = p->next;//新结点连入
    		p->next = L;//前链连接上新结点
    		L->data = p->data;//数据交换,实现前插
    		p->data = e;
    		return true;
    	}
    }
    

    在这种前插方式下,时间复杂度为O(1),而且不需要知道头指针

    如果给定的是需要前插的不是值,而是结点,具体的实现代码如下:

    bool InsertPriorNode(LNode* p, LNode *s) {//在p结点前面插入结点s
    	if ((p == NULL)||(s == NULL)) {
    		return false;
    	}
    	else {
    		s->next = p->next;//同样采用后插方式
    		p->next = s;
    		int temp;//具体实现时的数据类型可能并不是int,灵活变换即可
    		temp = s->data;//交换数据实现前插
    		s->data = p->data;
    		p->data = temp;
    		return true;
    	}
    }
    

    后插

    给定链表的一个结点,实现在此结点的后面插入一个节点,实现方式与前插类似,甚至更简单直观。

    bool InsertNextNode(LNode* p, int e) {//在p结点之后插入元素e
    	if (p == NULL) {
    		return false;
    	}
    	LNode* L = (LNode*)malloc(sizeof(LNode));
    	if (L == NULL) {
    		cout << "内存分配失败" << endl;
    		return false;
    	}
    	else {
    		L->next = p->next;
    		p->next = L;
    		L->data = e;
    		return true;
    	}
    }
    

    如果给定的是需要后插的不是值,而是结点,具体的实现代码如下:

    bool InsertNextNode(LNode* p, LNode* s) {//在p结点之后插入结点s
    	if ((p == NULL)||(s==NULL)) {
    		return false;
    	}
    	else {
    		s->next = p->next;
    		p->next = s;
    		return true;
    	}
    }
    

    查找

    在线性表的查找中,有两种查找方式。
    一种是按值查找,一种是按位查找
    因为是链式实现的线性表,所以这两种方式都需要遍历这个链表来查找,所以一般来说时间复杂度为O(n)

    按值查找代码如下

    LNode* LocateElem(LinkList L, int e) {
    	if (L == NULL) {
    		cout << "传入链表为空,查找失败!" << endl;
    		return NULL;	
    	}
    	else {
    		LNode* p;
    		p = L->next;//因为带头结点,所以会指向头结点的下一个结点
    		while ((p != NULL) && (p->data != e)) {
    			p = p->next;
    		}
    		return p;
    	}
    }
    

    按位查找代码如下

    LNode* GetElem(LinkList L, int i) {
    	int j = 1;//标记当前p指向第几个结点
    	LNode* p=L->next;
    	if (i == 0) {
    		return L;
    	}
    	if (i < 1) {
    		return NULL;
    	}
    	while ((p!=NULL)&&(j<i)) {
    		p = p->next;
    		j++;
    	}
    	return p;
    }
    

    建立单链表

    建立单链表可以采用两种方式,一种是头插法,一种是尾插法
    头插法是每次输入的都从头部插入,尾插法是每次输入都从尾部插入

    采用头插法可以用上面已经封装好的插入函数来实现

    头插法

    LinkList List_HeadInsert(LinkList& L) {
    	int a = 0;
    	while (true) {
    		cout << "请输入元素值:";
    		cin >> a;
    		if (a != 9999) {
    			InsertNextNode(L, a);
    		}
    		else {
    			break;
    		}
    	}
    	return L;
    }
    

    尾插法
    每次都要找到最后元素

    LinkList List_TailInsert(LinkList& L) {
    	int a;
    	LNode* p=L;
    	while (p->next != NULL) {
    		p = p->next;//找到最后元素
    	}
    	while (true) {
    		cout << "请输入要插入的元素的值:";
    		cin >> a;
    		if (a != 9999) {
    			LNode* s = (LNode*)malloc(sizeof(LNode));//创建新结点
    			s->data = a;//新结点的元素值为输入的a
    			p->next = s;//将新节点连上链表
    			s->next = NULL;//新的末尾要指NULL,防止出错
    			p = p->next;//p始终指向最后一个结点
    		}
    		else {
    			break;
    		}
    	}
    	return L;
    }
    

    删除

    删除结点有两种方式,一种需要知道头指针,一种只需要知道当前结点的指针即可
    需要知道头指针的删除

    bool ListDelete(LinkList& L, int i, int& e)
    {
    	LNode* p;
    	p=GetElem(L, i-1);//p指向要删除的前一个位置
    	if (p == NULL) {
    		//说明前一个结点都不存在,那么无法删除
    		return false;
    	}
    	else if (p->next == NULL) {
    		//说明输入要删除的结点本身就不存在,不需要删除,直接成功
    		return true;
    	}
    	else {
    		LNode* q = p->next;//q指向要删除的结点
    		e = q->data;//返回删除的值
    		p->next = q->next;//链接断开
    		free(q);//释放无用指针
    		return true;
    	}
    }
    

    不需要头指针的删除

    bool ListDelete(LNode* p, int& e) {
    	if (p == NULL) {
    		//说明这个结点本身就不存在
    		return false;
    	}
    	else if (p->next == NULL) {
    		//说明这个结点后面是没有结点的,那么这种删除只能通过从头结点查找上一个结点来删除,所以会失败
    		return false;
    	}
    	else {
    		e = p->data;//返回删除的值
    		LNode* s = p->next;
    		p->data = s->data;
    		p->next = s->next;
    		free(s);
    		return true;
    	}
    }
    

    求表长

    求表长比较简单,一个while循环遍历以下就行,时间复杂度为O(n)

    int GetListLength(LinkList L) {
    	int length = 0;
    	LNode* p = L;
    	if (p == NULL) {
    		//说明头结点的不存在,表还未创建
    		cout << "表还未创建!" << endl;
    		return -1;
    	}
    	else if (p->next == NULL) {
    		//说明表创建了,但是没有元素,那么长度为0
    		return 0;
    	}
    	else {
    		while (p->next != NULL) {
    			length++;
    			p = p->next;
    		}
    		return length;
    	}
    }
    

    总结

    单链表的具体实现还是比较简单的,主要是要弄清楚指针的指向,以及各种操作细节之处的先后顺序,如果顺序不当可能会导致最后结果的错误。

    以上是复习数据结构带头结点的单链表时做的一些笔记,难免有遗漏与错误之处,请不吝予以指正。

    展开全文
  • //打印单链表 public void display() {} 遍历单链表,输出每一个节点的data即可 //释放内存 public void clear(){} 当一个对象没有人引用的时候,就会被jvm回收掉,所以我们把this.head = null;没有人引用头节点,...
  • 也就是返回一个空的不带头结点的链表 当第一个数据合法时,循环输入,使用尾插法建立新结点后插,但是当我只输入了一个数这个程序就结束了,麻烦各位老师帮我看看是哪里出了问题 ...
  • 1.删除不带头结点单链表的第一个值为x的节点 #include"slnklist.h" linklist delx(linklist head, datatype x) { linklist p,pre; if (!head) { printf("链表为空!\n"); } p = head; pre = NULL; ...
  • 不带头结点单链表的创建(头插法和尾插法)

    千次阅读 多人点赞 2020-10-02 21:56:46
    1、用头插法建立不带头结点单链表 #include<iostream> using namespace std; //单链表的结构体 typedef struct Node { int data; struct Node *next; }Node; /*不带头结点单链表的创建(头插法)*/ ...
  • typedef struct LNode{ int data; struct LNode *next; }LNode, *LinkList; LinkList Reverse(LinkList &...//处理第一个结点 while(r!=NULL) { s=p; p=r; r=r->next; p->next=s; } L.
  • class Node(object): """节点""" def __init__(self, elem): self.elem = elem self.next = None ...# 不带头节点的单链表 class SingleLinkList(object): """单链表""" def __init__(self, node...
  • vs2013可能能运行 首先新建一个头文件slnklist.h #include <stdio.h> #include <stdlib.h> /**************************************/ /* 链表实现的头文件,文件名slnklist.h */ /****************...
  • 链接
  • 不带头结点单链表: 1.不带头结点单链表操作中,除了初始化,头插,尾插,删除,操作与带头结点的单链表有差别外,其它的操作基本上一样。 2.链表指针直接指向了首元节点,因此在首元节点前插入数据元素或者...
  • L是一个带头结点单链表,函数ListReverse_L(LinkList &L)要求在新开辟节点的前提下将单链表中的元素进行逆置,如原单链表元素依次为1,2,3,4,则逆置后为4,3,2,1。 函数接口定义: void ListReverse_L...
  • 利用c++实现不带头结点链表的基本操作实现,如逆序建立链表,插入、删除链表元素等。
  • 数据结构(带头结点单链表)

    千次阅读 2019-11-23 22:28:30
    数据结构 单链表 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点...带头结点单链表 头结点一般在栈区或者数据区开辟且头结点存储有...
  • 不带头结点单链表的基本操作

    千次阅读 2020-03-05 14:54:28
    定义结点 typedef struct LNode{ int data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList;...//初始化一个空的单链表 bool InitList(LinkList &L){ L = NU...
  • 不带头结点单链表的创建、插入、删除。 #include<stdio.h>#include<stdlib.h>typedef struct node{ int data; node *next;}node;//创建不带头结点的单链...
  • 下面简单介绍带头结点单链表中元素逆序的两种算法: 算法一:采用头插法 算法思想:采用头插法,依次顺序遍历链表元素,插入到头结点后 算法实现: LinkList Reverse(LinkList L){ //需要改变实参L的数值的时候...
  • 使用尾插法建立一个带头结点单链表,然后输出结果
  • 先找到第i-1个结点,然后用指针变量P指向它 然后生成一个新结点,用指针S指向它,然后数据域赋值为e,然后将它插入 ai变成了新结点的后继,s的next域赋值给ai这个结点的地址 而ai这个结点的地址在ai-1的next...
  • 带头结点单链表的实现(c语言)

    千次阅读 2020-09-14 09:59:17
    //这个程序是带头结点单链表的实现 /* 单链表链式存储结构 头指针与头结点的异同: 头指针: 1、头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针 2、无论链表是否为空,头指针均...
  • 带头结点单链表,将其翻转,输出。typedef struct lnode { int data; struct lnode *next;/*指针域*/ } lnode,*linklist; /**linklist表示struct lnode类型的指针;lnode是别名*/
  • 题目:设计一个递归算法,删除不带头结点单链表中所有值为x的结点。 代码实现 //设计一个递归算法,删除不带头结点单链表L中所有值为x的结点 #include"head.h"; typedef int Elemtype; //定义单链表 typedef ...
  • 不带头结点单链表代码实现

    千次阅读 2016-10-20 11:28:27
    不带头结点单链表代码实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,089
精华内容 2,035
关键字:

不带头结点建立单链表