2019-11-23 22:28:30 wfea_lff 阅读数 43
  • 数据结构实战完全手册

    数据结构是程序设计的必修知识,它是程序设计的基本功,并且在企业面试、日常工作、研究生入学考试中都占有重要的地位。不同于其他课程,本课程从单链表出发,手把手的全代码实现了栈与队列,树、图(包括数组和链表的两种形式),并对这些经典结构的应用也做了代码级的实现,覆盖了经典数据结构的全部内容. 课程参考教材:周幸妮教授的《数据结构与算法分析新视角》 由德古意特(DE GRUYTER. 德国)和科学出版社联合出版 对应英文版《Data Structures and Algorithms Analysis – New Perspectives》

    1247 人正在学习 去看看 夏曹俊

数据结构

单链表

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

带头结点的单链表

头结点一般在栈区或者数据区开辟且头结点不存储有效数据,头结点的数据域存储当前结点的的个数,除头结点外,其他结点在堆区开辟空间

一、创建带头结点的单链表
带头结点的单链表通过结构体和联合体一起创建

#define FALSE 0
#define TRUE  1

typedef int ElemType;

typedef union DataType
{
	ElemType value;
	int      num;
}DataType;

typedef struct LNode
{
	DataType  data;   //  数据元素或者个数
	struct LNode *next;  //  存储下一个数据结点的地址
}LNode, *LinkList;

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

二、单链表所实现的功能(带头结点的单链表)
1.找单链表前一个位置

static LinkList FindPrior_Pos(LinkList head, int pos)       //找前一个位置
{
	LinkList p = head;
	while(pos>0)
	{
		p = p->next;
		pos--;
	}
	return p;
}

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

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

3.单链表初始化

void Init_LinkList(LinkList head)       //初始化
{
	assert(head!=NULL);
	if(head==NULL) exit(0);
	head->next = NULL;
	head->data.num = 0;
}

4.插入
(1)位置插

int  Insert_LinkList_Pos(LinkList head, ElemType val, int pos)     //位置插
{
	if(head == NULL) exit(0);
	if(pos<0||pos>head->data.num)  return FALSE;
	LinkList p = FindPrior_Pos(head,pos);
	LinkList q = ApplyNode(val,p->next);
	if(q == NULL) return FALSE;
	p->next = q;
	head->data.num++;
	return TRUE;
}

(2)头插

int  Insert_LinkList_Head(LinkList head, ElemType val)         //头插
{
	if(head == NULL) exit(0);
	LinkList p = FindPrior_Pos(head,0);
	LinkList q = ApplyNode(val,p->next);
	if(q == NULL) return FALSE;
	p->next = q;
	head->data.num++;
	return TRUE;
}

(3)尾插

int  Insert_LinkList_Tail(LinkList head, ElemType val)        //尾插
{
	if(head == NULL) exit(0);
	LinkList p = FindPrior_Pos(head,head->data.num);
	LinkList q = ApplyNode(val,p->next);
	if(q == NULL) return FALSE;
	p->next = q;
	head->data.num++;
	return TRUE;
}

5.删除
(1)位置删

int  Delete_LinkList_Pos(LinkList head, int pos)        //位置删
{
	if(head == NULL)  exit(0);
	if(pos<-1||pos>=head->data.num)  return FALSE;
	LinkList p = FindPrior_Pos(head,pos);
	LinkList q = p->next;
	p->next = q->next;
	free(q);
	head->data.num--;
	return TRUE;
}

(2)头删

int  Delete_LinkList_Head(LinkList head)        //头删
{
	if(head == NULL)  exit(0);
	LinkList p =  FindPrior_Pos(head,0);
	LinkList q = p->next;
	p->next = q->next;
	free(q);
	head->data.num--;
	return TRUE;
}

(3)尾删

int  Delete_LinkList_Tail(LinkList head)        //尾删
{
	if(head == NULL)  exit(0);
	LinkList p =  FindPrior_Pos(head,head->data.num-1);
	LinkList q = p->next;
	p->next = q->next;
	free(q);
	head->data.num--;
	return NULL;
}

6.打印

void Show_LinkList(LinkList head)       //打印
{
	if(head == NULL)  exit(0);
	LinkList p = head->next;
	for(int i = 0;i<head->data.num;i++)
	{
		printf("%d  ",p->data.value);
		p = p->next;
	}
	printf("\n");
}

7.清空单链表

int  Clear_LinkList(LinkList head)      //清空
{
	if(head == NULL)  exit(0);
	while(head->data.num)
	{
		Delete_LinkList_Tail(head);
	}
	return TRUE;
}

8.销毁单链表

int  Destroy_LinkList(LinkList head)      //销毁
{
	return Clear_LinkList(head);
}

总代码:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define FALSE 0
#define TRUE  1

typedef int ElemType;

typedef union DataType
{
	ElemType value;
	int      num;
}DataType;

typedef struct LNode
{
	DataType  data;   //  数据元素或者个数
	struct LNode *next;  //  存储下一个数据结点的地址
}LNode, *LinkList;

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

static LinkList FindPrior_Pos(LinkList head, int pos)       //找前一个位置
{
	LinkList p = head;
	while(pos>0)
	{
		p = p->next;
		pos--;
	}
	return p;
}

void Init_LinkList(LinkList head)       //初始化
{
	assert(head!=NULL);
	if(head==NULL) exit(0);
	head->next = NULL;
	head->data.num = 0;
}

int  Insert_LinkList_Pos(LinkList head, ElemType val, int pos)     //位置插
{
	if(head == NULL) exit(0);
	if(pos<0||pos>head->data.num)  return FALSE;
	LinkList p = FindPrior_Pos(head,pos);
	LinkList q = ApplyNode(val,p->next);
	if(q == NULL) return FALSE;
	p->next = q;
	head->data.num++;
	return TRUE;
}

int  Insert_LinkList_Head(LinkList head, ElemType val)         //头插
{
	if(head == NULL) exit(0);
	LinkList p = FindPrior_Pos(head,0);
	LinkList q = ApplyNode(val,p->next);
	if(q == NULL) return FALSE;
	p->next = q;
	head->data.num++;
	return TRUE;
}

int  Insert_LinkList_Tail(LinkList head, ElemType val)        //尾插
{
	if(head == NULL) exit(0);
	LinkList p = FindPrior_Pos(head,head->data.num);
	LinkList q = ApplyNode(val,p->next);
	if(q == NULL) return FALSE;
	p->next = q;
	head->data.num++;
	return TRUE;
}

int  Delete_LinkList_Pos(LinkList head, int pos)        //位置删
{
	if(head == NULL)  exit(0);
	if(pos<-1||pos>=head->data.num)  return FALSE;
	LinkList p = FindPrior_Pos(head,pos);
	LinkList q = p->next;
	p->next = q->next;
	free(q);
	head->data.num--;
	return TRUE;
}

int  Delete_LinkList_Head(LinkList head)        //头删
{
	if(head == NULL)  exit(0);
	LinkList p =  FindPrior_Pos(head,0);
	LinkList q = p->next;
	p->next = q->next;
	free(q);
	head->data.num--;
	return TRUE;
}

int  Delete_LinkList_Tail(LinkList head)        //尾删
{
	if(head == NULL)  exit(0);
	LinkList p =  FindPrior_Pos(head,head->data.num-1);
	LinkList q = p->next;
	p->next = q->next;
	free(q);
	head->data.num--;
	return NULL;
}

int  Clear_LinkList(LinkList head)      //清空
{
	if(head == NULL)  exit(0);
	while(head->data.num)
	{
		Delete_LinkList_Tail(head);
	}
	return TRUE;
}

int  Destroy_LinkList(LinkList head)      //销毁
{
	return Clear_LinkList(head);
}

LinkList FindNode_Pos(LinkList head, int pos)       //查找
{
	if(head == NULL)  exit(0);
	if(pos<0||pos>head->data.num)  return NULL;
	LinkList p = FindPrior_Pos(head,pos);
	return p->next;
}

void Show_LinkList(LinkList head)       //打印
{
	if(head == NULL)  exit(0);
	LinkList p = head->next;
	for(int i = 0;i<head->data.num;i++)
	{
		printf("%d  ",p->data.value);
		p = p->next;
	}
	printf("\n");
}

int List(LinkList head,int k)      //删除倒数第k个
{
	if(head == NULL)
	{
		return FALSE;
	}
	LinkList p = head;
	LinkList q = head;
	for(int i=1;i<k;i++)
	{
		q = q->next;
	}
	while(q->next != NULL)
	{
		q = q->next;
		p = p->next;
	}
	return p->data.value;
}


int main()
{
	//以下为测试内容----------------------
	LNode head;
	Init_LinkList(&head);
	for(int i = 0;i<10;i++)
	{
		Insert_LinkList_Tail(&head,i);
	}
	Show_LinkList(&head);

	Insert_LinkList_Head(&head,100);
	Insert_LinkList_Pos(&head,200,head.data.num);
	Show_LinkList(&head);

	Delete_LinkList_Head(&head);
	Delete_LinkList_Tail(&head);
	Delete_LinkList_Pos(&head,head.data.num-1);
	Show_LinkList(&head);

	printf("%d\n",*(FindNode_Pos(&head,5)));

	Clear_LinkList(&head);
	Show_LinkList(&head);

	return 0;
}
2019-11-26 10:59:57 wfea_lff 阅读数 96
  • 数据结构实战完全手册

    数据结构是程序设计的必修知识,它是程序设计的基本功,并且在企业面试、日常工作、研究生入学考试中都占有重要的地位。不同于其他课程,本课程从单链表出发,手把手的全代码实现了栈与队列,树、图(包括数组和链表的两种形式),并对这些经典结构的应用也做了代码级的实现,覆盖了经典数据结构的全部内容. 课程参考教材:周幸妮教授的《数据结构与算法分析新视角》 由德古意特(DE GRUYTER. 德国)和科学出版社联合出版 对应英文版《Data Structures and Algorithms Analysis – New Perspectives》

    1247 人正在学习 去看看 夏曹俊

数据结构

单链表

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

不带头结点的单链表

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

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

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;
}
2018-11-06 19:41:01 Stephanie17395 阅读数 1827
  • 数据结构实战完全手册

    数据结构是程序设计的必修知识,它是程序设计的基本功,并且在企业面试、日常工作、研究生入学考试中都占有重要的地位。不同于其他课程,本课程从单链表出发,手把手的全代码实现了栈与队列,树、图(包括数组和链表的两种形式),并对这些经典结构的应用也做了代码级的实现,覆盖了经典数据结构的全部内容. 课程参考教材:周幸妮教授的《数据结构与算法分析新视角》 由德古意特(DE GRUYTER. 德国)和科学出版社联合出版 对应英文版《Data Structures and Algorithms Analysis – New Perspectives》

    1247 人正在学习 去看看 夏曹俊

单链表操作

删除单链表偶数节点

本题要求实现两个函数,分别将读入的数据存储为单链表、将链表中偶数值的结点删除。链表结点定义如下:
struct ListNode {
int data;
struct ListNode *next;
};

函数接口定义:

struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );

函数createlist从标准输入读入一系列正整数,按照读入顺序建立单链表。当读到−1时表示输入结束,函数应返回指向单链表头结点的指针。

函数deleteeven将单链表head中偶数值的结点删除,返回结果链表的头指针。

输入样例:

1 2 2 3 4 5 6 7 -1

输出样例:

1 3 5 7

AC代码:

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );
void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *head;

    head = createlist();
    head = deleteeven(head);
    printlist(head);

    return 0;
}
struct ListNode *createlist()
{
    struct ListNode *head,*p1,*p2;
    int temp;
    head=(struct ListNode *)malloc(sizeof(struct ListNode));
    p1=p2=(struct ListNode *)malloc(sizeof(struct ListNode));
    p1->next=p2->next=head->next=NULL;
    while(1)
    {
        scanf("%d",&temp);
        if(temp!=-1)
        {
            p1->data=temp;
            if(head->next==NULL)
                head->next=p1;
            else
            {
                p2->next=p1;
                p2=p1;
            }
            p1=(struct ListNode *)malloc(sizeof(struct ListNode));
            p1->next=NULL;
        }
        else
            break;
    }
    return head;
};
struct ListNode *deleteeven( struct ListNode *head )
{
    struct ListNode *temp,*p;
    p=head;
    temp=head->next;
    while(temp!=NULL)
    {
        if(temp->data%2==0)
            p->next=temp->next;
        else
            p=p->next;
        temp=temp->next;
    }
    return head->next;
};

2018-01-23 16:14:28 qq_33877149 阅读数 145
  • 数据结构实战完全手册

    数据结构是程序设计的必修知识,它是程序设计的基本功,并且在企业面试、日常工作、研究生入学考试中都占有重要的地位。不同于其他课程,本课程从单链表出发,手把手的全代码实现了栈与队列,树、图(包括数组和链表的两种形式),并对这些经典结构的应用也做了代码级的实现,覆盖了经典数据结构的全部内容. 课程参考教材:周幸妮教授的《数据结构与算法分析新视角》 由德古意特(DE GRUYTER. 德国)和科学出版社联合出版 对应英文版《Data Structures and Algorithms Analysis – New Perspectives》

    1247 人正在学习 去看看 夏曹俊

线性表的链式存储结构是指:用一组任意的存储单元(可以连续,也可以不连续)存储线性表中的数据单元。即逻辑上相邻的数据在计算机内的存储位置不一定相邻。如图所示:

    

这里具有一个数据域和多个指针域的存储单元通常称为 结点(node)。

在Java中没有显式的指针类型。然而实际上对象的访问就是使用指针来实现的,即在Java 中是使用对象的引用来替代指针的。

因此在使用 Java 实现该结点结构时,一个结点本身就是一个对象。我们定义一个先结点,为了提高复用性,在接口中定义了所有结点均支持的操作,即对结点中存储数据的存取。

/**
 * Created by Troshin on 2018/1/14.
 */
public interface Node {
    //获取结点数据域
    public Object getData();

    //设置结点数据域
    public void setData(Object obj);
}
单链表结点定义:

/**
 * Created by Troshin on 2018/1/14.
 */
public class SLNode implements Node {
    private Object element;
    private SLNode next;

    public SLNode(){
        this(null,null);
    }

    public SLNode(Object ele,SLNode next){
        this.element=ele;
        this.next=next;
    }

    public SLNode getNext() {
        return next;
    }

    public void setNext(SLNode next) {
        this.next = next;
    }

    /**
     * 接口实现
     * @return
     */
    @Override
    public Object getData() {
        return element;
    }

    @Override
    public void setData(Object obj) {
        this.element=obj;
    }
}
单链表是通过上述定义的结点使用 next 域依次串联在一起而形成的。


链表的第一个结点和最后一个结点,分别称为链表的 首结点和 尾结点。

尾结点的特征是其 next 引用为空(null),"^"表示"null"的意思。

与数组类似,单链表中的结点也具有一个线性次序,即如果结点 P 的 next 引用指向结点 S,则 P 就是 S 的直接前驱,S 是 P 的直接后续。单链表的一个重要特性:就是只能通过前驱结点找到后续结点,而无法从后续结点找到前驱结点。

我们先看看图解的查找、插入、删除操作:




除了查找操作外,插入和删除都给了三个不一样的方法,因此它们的时间复杂度也不一样,复杂度我们稍后讨论。现在我们看看方法的实现,方法的定义在上一章节,因此这里就不重复写了。

/**
 * Created by Troshin on 2018/1/14.
 */
public class ListSLinked implements myList {
    private Strategy strategy;      //数据元素比较策略
    private SLNode head;            //单链表首结点引用
    private int size;               //线性表中的数据元素的个数

    /**
     * 构造方法
     */
    public ListSLinked(){
        this(
                new DefaultStrategy());
    }

    public ListSLinked(Strategy strategy){
        this.strategy=strategy;
        head=new SLNode();
        size=0;
    }
    /**
     * 辅助方法:获取数据元素 e 所在结点的前驱结点
     */
    private SLNode getPreNode(Object e){
        SLNode p=head;
        while (p.getNext()!=null)
            if(strategy.equal(p.getNext().getData(),e))
                return  p;
            else p=p.getNext();
        return null;
    }

    /**
     * 辅助方法:获取序号为 0<=i<size 的元素所在结点的前驱结点
     * @return
     */
    private SLNode getPreNode(int i){
        SLNode p =head;
        for (;i>0;i--)
            p=p.getNext();
        return p;
    }

    /**
     * 获取序号为 0<=i<size 的元素所在结点
     * @param i
     * @return
     */
    private SLNode getNode(int i){
        SLNode p=head.getNext();
        for (;i>0;i--)
            p=p.getNext();
        return p;
    }

    /**
     * 返回线性表的大小,即数据元素的个数。
     * @return
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 如果线性表为空返回 true,否则返回 false。
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size==0;
    }

    /**
     * 判断线性表是否包含数据元素 e
     * @param e
     * @return
     */
    @Override
    public boolean contains(Object e) {
        SLNode p=head.getNext();
        while (p!=null)
            if (strategy.equal(p.getData(),e))
                return true;
            else p=p.getNext();
        return false;
    }

    /**
     * 返回数据元素 e 在线性表中的序号
     * @param e
     * @return
     */
    @Override
    public int indexOf(Object e) {
        SLNode p=head.getNext();
        int index=0;
        while (p!=null)
            if (strategy.equal(p.getData(),e))
                return index;
            else {
                index ++;
                p=p.getNext();
            }
        return -1;
    }

    /**
     * 将数据元素 e 插入到线性表中 i 号位置
     * @param i
     * @param e
     * @throws OutOfBoundaryException
     */
    @Override
    public void insert(int i, Object e) throws OutOfBoundaryException {
        if (i<0||i>size)
            throw new OutOfBoundaryException("错误,指定插入的序号越界");
        SLNode p=getPreNode(i);
        SLNode q=new SLNode(e,p.getNext());
        p.setNext(q);
        size ++;
        return;
    }

    /**
     * 将数据元素 e 插入到元素 obj 之前
     * @param obj
     * @param e
     * @return
     */
    @Override
    public boolean insertBefore(Object obj, Object e) {
        SLNode p =getPreNode(obj);
        if (p!=null) {
            SLNode q = new SLNode(e,p.getNext());
            p.setNext(q);
            size++;
            return true;
        }
        return false;
    }

    /**
     * 将数据元素 e 插入到元素 obj 之后
     * @param obj
     * @param e
     * @return
     */
    @Override
    public boolean insertAfter(Object obj, Object e) {
        SLNode p=head.getNext();
        while (p!=null)
            if (strategy.equal(p.getData(),obj)) {
                SLNode q = new SLNode(e, p.getNext());
                p.setNext(q);
                size ++;
                return true;
            }
            else p=p.getNext();
        return false;
    }

    /**
     * 删除线性表中序号为 i 的元素,并返回之
     * @param i
     * @return
     * @throws OutOfBoundaryException
     */
    @Override
    public Object remove(int i) throws OutOfBoundaryException {
        if (i<0||i>size)
            throw new OutOfBoundaryException("错误,指定删除的序号越界");
        SLNode p=getPreNode(i);
        Object obj=p.getNext().getData();
        p.setNext(p.getNext().getNext());
        size --;
        return obj;
    }

    /**
     * /删除线性表中第一个与 e 相同的元素
     * @param e
     * @return
     */
    @Override
    public boolean remove(Object e) {
        SLNode p=getPreNode(e);
        if (p!=null){
            p.setNext(p.getNext().getNext());
            size --;
            return true;
        }
        return false;
    }

    /**
     * 替换线性表中序号为 i 的数据元素为 e,返回原数据元素
     * @param i
     * @param e
     * @return
     * @throws OutOfBoundaryException
     */
    @Override
    public Object replace(int i, Object e) throws OutOfBoundaryException {
        if (i>0 || i>=size)
            throw new OutOfBoundaryException("错误,指定的序号越界");
        SLNode p=getNode(i);
        Object obj=p.getData();
        p.setData(e);
        return obj;
    }

    /**
     * 返回线性表中序号为 i 的数据元素
     * @param i
     * @return
     * @throws OutOfBoundaryException
     */
    @Override
    public Object get(int i) throws OutOfBoundaryException {
        if (i<0 || i>=size)
            throw new OutOfBoundaryException("错误,指定的序号越界");
        SLNode p=getNode(i);
        return p.getData();
    }
}

方法 getSize()、isEmpty()的时间复杂度均为Θ(1)。通过成员变量 size 可以直接判断出线性表中数据元素的个数以及线性表是否为空。


方法 getPreNode(Object e)、getPreNode(int i),其功能是找到数据元素 e 或线性表中 i 号数据元素所在结点的前驱结点。这两个方法的平均运行时间 T(n)≈n/2。


方法 replace(int i, Object e)、get(int i)的平均运行时间 T(n)≈n/2,比使用数组实现相应操作要慢得多。


方法  contains(Object e)、indexOf(Object e)主要是在线性表中查找某个数据元素。方法平均运行时间与使用数组的实现一样,都需要从线性表中 0 号元素出发,依次向后查找,因此方法运行时间 T(n) ≈ n/2。


方法 insert(int i, Object e)、remove(int i)的运行时间 T(n)≈n/2,与使用数组实现的运行时间相同。


方法 insertBefore(Object obj, Object e)、insertAfter(Object obj, Object e)、remove(Object e)的平均运行时间 T(n)≈n/2 < n,要优于使用数组实现的运行时间。


数组,即顺序存储结构(顺序表)。



初入数据结构,以学习总结为主,如果写的不详细或者有什么其它错误的地方希望各位dalao们指点指点。

参考的书籍:《数据结构-JAVA版》《数据结构与算法》








2019-09-17 16:54:29 d__yz 阅读数 30
  • 数据结构实战完全手册

    数据结构是程序设计的必修知识,它是程序设计的基本功,并且在企业面试、日常工作、研究生入学考试中都占有重要的地位。不同于其他课程,本课程从单链表出发,手把手的全代码实现了栈与队列,树、图(包括数组和链表的两种形式),并对这些经典结构的应用也做了代码级的实现,覆盖了经典数据结构的全部内容. 课程参考教材:周幸妮教授的《数据结构与算法分析新视角》 由德古意特(DE GRUYTER. 德国)和科学出版社联合出版 对应英文版《Data Structures and Algorithms Analysis – New Perspectives》

    1247 人正在学习 去看看 夏曹俊

**

存在一个含有n个元素的单链表,将第i-1个结点与第i个结点互换,指针不变

**

#include<stdio.h>
#include<malloc.h> 

//有一个n个结点的单链表 ,将第i-1个结点与第i个结点互换,指针不变 
typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

/*带头结点的单链表数据元素的访问 */ 
void ListTraverse(LinkList L, void (*visit)(LNode*))
{
	LNode *p=L->next;
	while(p)
	{
		visit(p);
		p=p->next;
	}
	printf("\n");
}
void visit(LNode *p)
{
	printf("%d ",p->data);
}
int main()
{
	//初始化一个单链表
	LNode *L,*p,*r,*q,*q1;
	int n;
	scanf("%d",&n);
	L=(LNode*)malloc(sizeof(LNode));
	L->next=NULL;
	r=L;
	ElemType e;
	while(n--){
		p=(LNode*)malloc(sizeof(LNode));
		scanf("%d",&e);
		p->data=e;
		p->next=r->next;
		r->next=p;
		r=p;
	} 
	//遍历该单链表,查看创建是否成功! 
	ListTraverse(L,visit); 
	//第i-1个结点与第i个结点互换,指针不变 
	int j=0;
	q=L;
	int k;
	// k指的是第i个元素
	scanf("%d",&k);
	while(q && j<k)
	{
		q1=q;
		q=q->next;
		j++;
	}
	//退出循环,q1是第i-1个元素 
	if(q==NULL)
		return 0;
	else{
//		printf("%d",q1->data);
		ElemType e1=q1->data;
		q1->data = q1->next->data;
		q1->next->data =e1;
	}
	ListTraverse(L,visit);
}
/*
5
1 2 3 4 5
*/

在这里插入图片描述

没有更多推荐了,返回首页