1. 全栈程序员必看首页

数据结构(1)-线性表「建议收藏」

全栈程序员-站长 • • 未分类 • 阅读 34

数据结构(1)-线性表「建议收藏」1.线性表：n个数据元素的有序集合。线性表是一种常用的数据结构。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。　　线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有

大家好，又见面了，我是你们的朋友全栈君。

 

 

一. 线性表：n个数据元素的有序集合。

线性表是一种常用的数据结构。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。　　线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。

特征：

1．集合中必存在唯一的一个“第一元素”；
2．集合中必存在唯一的一个 “最后元素” ；
3．除最后一个元素之外，均有 唯一的后继(后件)；
4．除第一个元素之外，均有 唯一的前驱(前件)。

java中的List接口，就是线性表。ArrayList就是顺序线性表，LinkedList就是链表线性表。

 

二. 线性表的顺序表示：ArrayList

一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。

优点：在于随机访问元素，

缺点：插入和和删除的时候，需要移动大量的元素。

1、c语言实现代码：

// Test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include "stdlib.h"
//宏定义
#define TRUE   1
#define FALSE   0
#define OK    1
#define ERROR   0
#define INFEASIBLE -1
#define OVERFLOW -2

#define LT(a,b)   ((a)<(b))
#define N = 100       

#define LIST_INIT_SIZE 100 //线性表初始空间分配量
#define LISTINCREMENT   10 //线性表空间分配的增量

typedef int Status;
typedef int ElemType;

typedef struct LNode{
	ElemType  *elem;        //存储空间的基地址
	int      lenght;		//当前的长度
	int		 listsize;      //当前分配的存储容量
}SqList;

/**
 *构造空的线性表
 */

Status initList(SqList &L, int lenght){
	if (lenght == 0) lenght = LIST_INIT_SIZE;
	L.elem = (ElemType *)malloc(lenght * sizeof(ElemType));
	if(!L.elem) exit(OVERFLOW);  //分配存储空间失败
	L.lenght = 0;				 //初始空表长度为0
	L.listsize = lenght ;//初始存储容量为100
	return OK;
}
/************************************************************************/
/* 在第i位置插入e
*/
/************************************************************************/
Status insertList(SqList &L, ElemType e, int i){
	ElemType *p,  *q;
	if(i<0 ||i > L.lenght) return ERROR;  //i值不合法
	if (L.lenght >= L.listsize) {
		ElemType *newbase = (ElemType *)realloc(L.elem ,(L.listsize +LISTINCREMENT)*sizeof(ElemType));
		if(!newbase) return OVERFLOW;	//存储分配失败  
		L.elem = newbase;				//新基值
		L.listsize += LISTINCREMENT;    //增加存储容量
	}
	q = &L.elem[i];						//q为插入的位置
	for (p = &L.elem[L.lenght]; p>=q; --p) {
		*p = *(p-1);					//i元素之后的元素往后移动
	}
	*q = e;								//插入e
	L.lenght +=1;
	return OK;

}
/************************************************************************/
/* 快速排序 
*/
/************************************************************************/
void sortList(SqList &L){
	

}
/************************************************************************/
/* 删除第i位置元素，并用e返回其值                                                                     */
/************************************************************************/
Status deleteListElem(SqList &L, int i, ElemType &e){
	int *p,  *q;
	if(i<0 ||i > L.lenght) return ERROR;  //i值不合法
	q = &L.elem[i];						  //被删除元素的位置为i，L.elem就是数组名,
	e = *q;								  //被删除元素的值赋值给e
	for (p = q; p< (L.elem + L.lenght); p++){ //元素左移
		*p = *(p+1);
	}
	--L.lenght;
	return OK;
}

/************************************************************************/
/*  快速排序
*/
/************************************************************************/

int partition(SqList &L, ElemType low, ElemType high){
	ElemType pivotkey = L.elem[low];		       //枢轴记录关键字
	while (low < high) {					 //从表的两端向中间扫描
		while (low < high &&  L.elem[high] >= pivotkey ) --high;//高端位置扫描
		L.elem[low] = L.elem[high];		//交换数据，小于pivotkey移到低端
		L.elem[high] = pivotkey;

		while (low < high && L.elem[low] <= pivotkey ) ++low;     //低端扫描
		L.elem[high] = L.elem[low];				  //交换数据 大于pivotkey移到高端
		L.elem[low] = pivotkey;									
	}
	return low;
}

void quickSort(SqList &L, ElemType low, ElemType high){
	int pivot;
	if(low < high) {										   
		pivot =  partition(L,  low,  high); 	
		quickSort(L,  low,  pivot -1);			//低端子表排序
		quickSort(L,  pivot +1, high);			//高端子表排序
	}
	
}


/************************************************************************/
/* 
合并两个线性表
*/
/************************************************************************/

void mergeList(SqList La, SqList Lb,  SqList &Lc){
	ElemType *pa, *pb, *pc;
	Lc.listsize =  La.lenght + Lb.lenght;
	initList(Lc, Lc.listsize);			//初始化LC\pc = Lc.elem;
	Lc.lenght = Lc.listsize;
	pc = Lc.elem;
	pa = La.elem;
	pb = Lb.elem;
	while (pa <= &La.elem[La.lenght -1] && pb <= &Lb.elem[Lb.lenght -1]){
		if (*pa <= *pb) *pc++ = *pa++;
		else *pc++ = *pb++;
	}
	while(pa <= &La.elem[La.lenght -1]) *pc++ = *pa++; //插入La的剩余元素
	while(pb <= &Lb.elem[Lb.lenght -1]) *pc++ = *pb++; //插入Lb的剩余元素

}

/************************************************************************/
/* 打印list
*/
/************************************************************************/
void printList(SqList L){
	printf("当前值:"); 
	for (int i =0; i<L.lenght;i++) {
		printf("%d ", *(L.elem+i)); // L.elem为首地址
	} 
	printf("\r\n"); 
}

void main()
{
	SqList La,Lb,Lc;
	ElemType e;
	int init,i;
	init = initList(La, LIST_INIT_SIZE);
	int data[6] = {5,3,6,2,7,4};
	for (i=0; i<6;i++) {
		insertList(La,  data[i],  i);
	}
	printf("LA:\r\n"); 
	printList(La);
	deleteListElem(La, 3, e );
	printList(La);
	insertList(La,  e,  3);
	printList(La);

	//排序
	quickSort(La,0, La.lenght-1);
	printList(La);

	printf("LB:\r\n"); 
	initList(Lb, LIST_INIT_SIZE);
	int Bdata[5] = {1,3,2,4,6};
	for (i=0; i<5;i++) {
		insertList(Lb,  Bdata[i],  i);
	}
	//排序
	quickSort(Lb,0, Lb.lenght-1);
	printList(Lb);

	mergeList(La, Lb,  Lc);
	printList(Lc);

}

2、简单的java实现：

package com.javademo.demo.datastructure;

public class MyArrayList {
    //用来保存数据的数组
    private Integer[]  list ;
    //数组的默认大小
    private static final int DEFAULT_SIZE= 10;
    //数组的大小
    private int size;
    //线性表的最后元素的位置
    private int end;

    public MyArrayList(){
        list = new Integer[DEFAULT_SIZE];
        this.size = DEFAULT_SIZE;
        this.end = -1;
    }
    public MyArrayList(int initSize){
        list = new Integer[initSize];
        this.size = initSize;
        this.end = -1;
    }

    public void insert(int element, int i) throws Exception{
        if (this.end >= this.size){
            throw new Exception("线性表已满");
        }
        if (i < 0 || i > this.end + 1  ){
            throw new Exception("插入位置不合法:" + i);
        }
        this.end++;
        // 将位序i之后的元素向后移动
        for (int j = this.end; j > i ; j--) {
            list[j ] = list[j-1];
        }
        list[i] = element;
    }
    private void print() {
        for (int i = 0; i <= end; i++) {
            System.out.print(list[i] + "\t");
        }
        System.out.println();
    }

    public static void  main(String[] args) throws Exception{
        MyArrayList myArrayList = new MyArrayList(5);
        myArrayList.insert(22, 0);
        myArrayList.insert(33, 1);
        myArrayList.insert(44, 2);
        myArrayList.insert(55, 1);
        myArrayList.insert(66, 3);
        myArrayList.print();
        myArrayList.insert(11, 0);
        myArrayList.print();
    }
}

 

 

 

三. 线性表的链表表示LinkedList

一般使用链表来描述。

 

优点：对于新增和删除操作add和remove和方便。不需要移动元素。

缺点：不方便随机访问元素，LinkedList要移动指针

1、c++代码实现

// Test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include "stdlib.h"
//宏定义
#define TRUE   1
#define FALSE   0
#define OK    1
#define ERROR   0
#define INFEASIBLE -1
#define OVERFLOW -2

#define LT(a,b)   ((a)<(b))
#define N = 100       

typedef int Status;
typedef int ElemType;

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

/************************************************************************/
/*
初始化链表
*/
/************************************************************************/
Status initList(LinkList &L){
	/*单链表的初始化*/
	L = (LinkList)malloc(sizeof(LNode));    //申请一个头节点
	if(!L) exit(OVERFLOW);			//申请空间失败  
	L->next=NULL;				//建立一个带都节点的空链表
	return OK;

	/* 
	需要改变指针的指针，所以参数必须是引用或者是 *L:
	(*L) = (Lnode *)malloc(sizeof(Lnode));
	(*L)->next=NULL;
	return 1;                                                                     
	*/

}

/************************************************************************/
/*     
创建链表
*/
/************************************************************************/
void createList(LinkList L, int n){
	/*单链表的初始化*/
	if (!L) {
		initList(L);
	}
	ElemType data;
	LinkList p,q = L;
	printf("输入节点数据的个数%d：\r\n", n);
	for(int i = 0; i<n; i++) {
		p = (LinkList) malloc( sizeof(LNode)); //申请一个新节点
		scanf("%d",&data);
		p->data = data;
		p->next = q->next;
		q->next = p;
		q = p;
	}
}
/************************************************************************/
/* 在第i位置插入e
*/
/************************************************************************/
Status insertList(LinkList L, ElemType e, int i){
	LinkList s, p = L;
	int j = 0;
	while (p && j<i){				//寻找i节点
		p = p->next;
		j++;
	}
	if (!p ||j >i) return ERROR;
	s = (LinkList) malloc(sizeof(LNode));		//生成新节点
	s->data = e; s->next = p->next;			//插入L中
	p->next = s;
	return OK;

}

/************************************************************************/
/* 删除第i位置元素，并用e返回其值                                                                     */
/************************************************************************/
Status deleteListElem(LinkList L, int i, ElemType &e){
	LinkList p, q;
	int j = 0;
	p = L;
	while (p && j<i){
		p = p->next;
		++j;
	}
	if (!p->next || j>i)  return ERROR;   //删除的位置不对
	q  = p->next; p->next = q->next;
	e = q->data; free(q);			//释放节点
	return OK;
}


/************************************************************************/  
/*  插入排序 
*/  
/************************************************************************/  

void  InsertSort(LinkList L)
{
	LinkList  list;				/*为原链表剩下用于直接插入排序的节点头指针*/
	LinkList  node;				/*插入节点*/
	LinkList  p;		
	LinkList  q;		

	list = L->next;				/*原链表剩下用于直接插入排序的节点链表*/
	L->next = NULL;				/*只含有一个节点的链表的有序链表。*/
	while (list != NULL)   {	/*遍历剩下无序的链表*/
		node = list, q = L;   
		while (q && node->data > q->data  ) {
			p = q;
			q = q->next;
		}
		
		if (q == L) {  /*插在第一个节点之前*/
			L = node;
		}  else {	  /*p是q的前驱*/
			p->next = node;   
		}
		list = list->next;
		node->next = q; /*完成插入动作*/

	}
}



/************************************************************************/
/* 
合并两个线性表
*/
/************************************************************************/

void mergeList(LinkList  &La, LinkList  &Lb,  LinkList &Lc){
	LinkList pa, pb, pc;
	pa	= La->next;
	pb	= Lb->next;
	Lc =  pc = La;
	while (pa && pa) {
		if (pa->data > pb->data) {
			pc->next = pb;
			pc = pb;
			pb =pb->next;
		}else{
			pc->next = pa;
			pc = pa; 
			pa =pa->next;
		}
	}
	pc->next = pa? pa :pb;
	free(Lb);
}

/************************************************************************/
/* 打印list
*/
/************************************************************************/
void printList(LinkList  L){
	printf("当前值:");
	LinkList p;
	p = L->next;
	while(p){
		printf("%d ", p->data); 
		p = p->next;
	}
	printf("\r\n"); 
}

void main()
{
	LinkList  La,Lb,Lc;
	ElemType e;
	int init,i;
	printf("LA:\r\n");  
	initList(La);
	createList(La, 5);
	insertList(La, 7,  3);  
	printList(La);
	deleteListElem(La, 3,  e);  
	printList(La);
	InsertSort(La);
	printList(La);

	printf("Lb:\r\n");  
	initList(Lb);
	createList(Lb, 4);
	InsertSort(Lb);
	printList(Lb);

	printf("Lc:\r\n"); 
	initList(Lc);
	mergeList(La,   Lb,   Lc);
	printList(Lc);

}

2、java的单向链表实现：

package com.javademo.demo.datastructure;

import com.sun.org.apache.bcel.internal.ExceptionConst;

//泛型单向链表
public class MyLinkedList <T> {
    private static class  LNode<T>{
        public LNode<T> next;//指向后继结点
        public T data;  //存储数据
        public LNode(LNode<T> next,T data)
        {
            this.next = next;
            this.data = data;
        }
    }
     private  LNode head;//链表头节点
     private  LNode rear;//链表尾节点
     private int length; //链表的长度
     //初始化空链表
     public void MyLinkedList(){
         this.head = null;
         this.rear = null;
         this.length = 0;
     }
     public void insert(T data) {
         LNode node = new LNode<T>(null, data);
         if (this.length == 0) {
             head = node;
             rear = node;
         } else {
             rear.next = node;
             rear = node;
         }
         this.length++;
     }
    public void delete(int i) throws Exception{
         if (i > length) {
             throw new Exception("删除位置不对");
         }
         LNode p = head;
         int j = 0;
         while (p !=null && j < i-1 ) {
             p = p.next;
             j++;
         }
         LNode q = p.next; p.next = q.next;
         this.length--;
    }
     public void print(){
         LNode node = head;
         System.out.println("print:");
         while (node != null) {
            System.out.print(node.data + "\t");
            node = node.next;
         }
     }
     public static void main(String args[]) throws Exception{
         MyLinkedList<Integer> list = new MyLinkedList<Integer>();
         list.insert(1);
         list.insert(2);
         list.insert(3);
         list.insert(4);
         list.insert(5);
         list.print();
         list.delete(3);
         list.print();
     }
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/144685.html原文链接：https://javaforall.net

赞 (0)
全栈程序员-站长的头像全栈程序员-站长
0 0


相关推荐

  • navicat 生成激活码(注册激活) idea

    navicat 生成激活码(注册激活)

    (navicat 生成激活码)本文适用于JetBrains家族所有ide，包括IntelliJidea，phpstorm，webstorm，pycharm，datagrip等。IntelliJ2021最新激活注册码，破解教程可免费永久激活，亲测有效，下面是详细链接哦~https://javaforall.net/100143.html…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年3月22日
    181
  • nvue踩坑2

    nvue踩坑2

    nvue踩坑2小透明继续写一个 继上次的探索之后又遇到了一些问题 我来再说两句吧 希望能给同样遇到问题的朋友一点启发 1 关于图片圆角 因为我做的页面上面有出现用户头像 是圆形的 需要做成图片圆角 看了一些别人的博客 他们说是在 image 外层的父容器 div 的样式上加上圆角 然后用 overflow 来切掉它 让图片变圆 可是我尝试了以后发现并没有成功 然后 我把关注点从 div 上挪开 改成在 image 上加上 border radius 就成功了 写成 50 image div div image

    全栈程序员-站长的头像 全栈程序员-站长
    2025年11月9日
    2
  • 好未来第一届PHP开源技术大会资料分享「建议收藏」

    好未来第一届PHP开源技术大会资料分享「建议收藏」

    好未来第一届PHP开源技术大会资料分享

    全栈程序员-站长的头像 全栈程序员-站长
    2022年2月17日
    171
  • Python源代码_源代码版权和软件著作权

    Python源代码_源代码版权和软件著作权

    Python源代码_源代码版权和软件著作权一个小需求：在申请软件著作权的时候，需要提交一页50行，总共60页的源代码。但是设计的项目保存在多级的目录下，不想一个一个复制，遂通过python，os模块获得全部目录的文件，re正则化过滤无效源代码，然后基于docx模块写入到word中。涉及的模块有os,docx,re同学们要自行下载上述的模块，使用pipinstallXXX就可以的。。python大法好呀那我们就分为2个大的…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年9月22日
    2
  • 服务器地址和端口号是什么怎么看_常见服务对应的端口号

    服务器地址和端口号是什么怎么看_常见服务对应的端口号

    服务器地址和端口号是什么怎么看_常见服务对应的端口号常用端口号与对应的服务以及端口关闭端口简介：本文介绍端口的概念，分类，以及如何关闭/开启一个端口21端口：21端口主要用于FTP（FileTransferProtocol，文件传输协议）服务。

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月4日
    9
  • python进阶（13）装饰器[通俗易懂]

    python进阶（13）装饰器[通俗易懂]

    python进阶（13）装饰器[通俗易懂]装饰器装饰器放在一个函数开始定义的地方，它就像一顶帽子一样戴在这个函数的头上。和这个函数绑定在一起。在我们调用这个函数的时候，第一件事并不是执行这个函数，而是将这个函数做为参数传入它头顶上这顶帽子，

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月28日
    9

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号