数据结构(1)-线性表

古城微笑少年丶 2022-06-10 00:14 209阅读 0赞

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

--------------------

线性表是一种常用的[数据结构][Link 1]。在实际应用中，线性表都是以[栈][Link 2]、队列、[字符串][Link 3]、[数组][Link 4]等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。　　线性表是一个线性结构，它是一个含有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();
         }
    }

# #

[Link 1]: http://baike.baidu.com/view/9900.htm
[Link 2]: http://baike.baidu.com/view/38877.htm
[Link 3]: http://baike.baidu.com/view/56072.htm
[Link 4]: http://baike.baidu.com/view/209670.htm