#include<malloc.h>
typedef char ElemType
typedef struct LNode
{ElemType data
struct LNode *next
}LinkList
void CreatListF(LinkList *&L,ElemType a[],int n) //头插法建表
{
LinkList *sint i
L=(LinkList *)malloc(sizeof(LinkList))
L->next=NULL
for(i=0i<ni++)
{
s=(LinkList *)malloc(sizeof(LinkList))
s->data=a[i]
s->next=L->next
L->next=s
}
}
void CreateListR(LinkList *&L,ElemType a[],int n) //尾插法建表
{
LinkList *s,*rint i
L=(LinkList *)malloc(sizeof(LinkList))
r=L
for(i=0i<ni++)
{
s=(LinkList *)malloc(sizeof(LinkList))
s->data=a[i]
r->next=s
r=s
}
r->next=NULL
}
void InitList(LinkList *&L)//初始化线性表
{
L=(LinkList *)malloc(sizeof(LinkList))
L->next=NULL
}
void DestroyList(LinkList *&L) //销毁线性表
{
LinkList *p=L,*q=p->next
while(q!=NULL)
{
free(p)
p=q
q=p->next
}
free(p)
}
int ListEmpty(LinkList *L)//判断线性表是否为空
{
return(L->next==NULL)
}
int ListLength(LinkList *L)//求线性表的长度
{
LinkList *p=Lint n=0
while(p->next!=NULL)
{
n++p=p->next
}
return(n)
}
void DispList(LinkList *L) //输出线性表
{
LinkList *p=L->next
while(p!=NULL)
{
printf("%c",p->data)
p=p->next
}
}
int GetElem(LinkList *L,int i,ElemType &e) //求线性表中某个数据元素值
{
int j=0
LinkList *p=L
while(j<i&&p!=NULL)
{
j++p=p->next
}
if(p==NULL)
return 0
else
{
e=p->datareturn 1
}
}
int LocateElem(LinkList *L,ElemType e)//按元素值查找
{
LinkList *p=L->next
int i=1
while(p!=NULL&&p->data!=e)
{
p=p->nexti++
}
if(p==NULL)return(0)
else return(i)
}
int ListInsert(LinkList *&L,int i,ElemType e) //插入数据元素
{
int j=0
LinkList *p=L,*s
while(j<i-1&&p!=NULL)
{
j++p=p->next
}
if(p==NULL)return 0
else
{
s=(LinkList *)malloc(sizeof(LinkList))
s->data=es->next=p->nextp->next=s
return 1
}
}
int ListDelete(LinkList *&L,int i,ElemType &e) //删除数据元素
{
int j=0
LinkList *p=L,*q
while(j<i-1&&p!=NULL)
{
j++p=p->next
}
if(p==NULL)
return 0
else
{
q=p->next
if(q==NULL)return 0
e=q->data
p->next=q->next
free(q)
return 1
}
}
int main()
{
ElemType e,a[5]={'a','b','c','d','e'}
LinkList *h
InitList(h) //初始化顺序表h
CreateListR(h,&a[0],5)//依次采用尾插入法插入a,b,c,d,e元素
printf("单链表为:")
DispList(h) printf("\n")//输出顺序表h
printf("该单链表的长度为:")
printf("%d",ListLength(h))printf("\n") //输出顺序表h的长度
if(ListEmpty(h)) printf("该单链表为空。\n")
else printf("该单链表不为空。\n") //判断顺序表h是否为空
GetElem(h,3,e)printf("该单链表的第3个元素为:")
printf("%c",e)printf("\n") //输出顺序表h的第3个元素
printf("该单链表中a的位置为:")
printf("%d",LocateElem(h,'a'))printf("\n") //输出元素'a'的位置
ListInsert(h,4,'f') //在第4个元素位置插入'f'素
printf("在第4 个元素位置上插入'f'后单链表为:")
DispList(h)printf("\n") //输出顺序表h
ListDelete(h,3,e) //删除L的第3个元素
printf("删除第3个元素后单链表为:")
DispList(h)printf("\n") //输出顺序表h
DestroyList(h)//释放顺序表h
return 0
}
代码如下:
头文件:
2_1.h
#ifndef _2_1_H
#define _2_1_H
typedef void SeqList
typedef void SeqListNode
//创建线性表
SeqList * SeqList_Create(int capacity)
//销毁线性表
void SeqList_DesTroy(SeqList * list)
void SeqList_Clear(SeqList* list)
int SeqList_Length(SeqList* list)
int SeqList_Capacity(SeqList* list)
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
SeqListNode* SeqList_Get(SeqList* list, int pos)
SeqListNode* SeqList_Delete(SeqList* list, int pos)
#endif
源文件:
// 顺序线性表.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <malloc.h>
#include <stdlib.h>
#include "2_1.h"
typedef unsigned int TSeqListNode
typedef struct {
int len //长度
int capacity//总长度
TSeqListNode * node//每个节点的指针
} TSeqList
int main()
{
SeqList* list = SeqList_Create(5)//创建线性表
int i = 6//赋值6个变量,已超过线性表最大值 5
int j = 1
int k = 2
int x = 3
int y = 4
int z = 5
int index = 0
SeqList_Insert(list, &i, 7) //将这6个变量插入线性表中
SeqList_Insert(list, &j, 0)
SeqList_Insert(list, &k, 0)
SeqList_Insert(list, &x, 0)
SeqList_Insert(list, &y, 0)
SeqList_Insert(list, &z, 0)
//遍历
for(index=0index<SeqList_Length(list)index++)
{
int* p = (int*)SeqList_Get(list, index)
printf("%d ", *p)
}
printf("\n")
//删除操作
while( SeqList_Length(list) >0 )
{
int* p = (int*)SeqList_Delete(list, 0)
printf("删除了: %d\n", *p)
}
SeqList_Clear(list)
SeqList_DesTroy(list)
system("pause")
return 0
}
//创建线性表
SeqList * SeqList_Create(int capacity)
{
TSeqList* ret = NULL
if(capacity >= 0)
{
ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode)*capacity) //为线性表分配空间,包含结 //构体和节点的总大小
}
if(NULL != ret)
{
ret->len = 0
ret->capacity = capacity
ret->node = (TSeqListNode*)(ret + 1)//将节点指向上述分配到的空间的后部分
}
return ret
}
//销毁
void SeqList_DesTroy(SeqList * list)
{
free(list)
}
//清空
void SeqList_Clear(SeqList* list)
{
TSeqList * ret = (TSeqList*)list
if(NULL != ret)
{
ret->len = 0
}
}
//获得线性表的长度
int SeqList_Length(SeqList* list)
{
TSeqList * ret = (TSeqList*)list
int len = -1
if(NULL != ret)
{
len = ret->len
}
return len
}
//线性表的总长度
int SeqList_Capacity(SeqList* list)
{
TSeqList * ret = (TSeqList*)list
int capacity = -1
if(NULL != ret)
{
ret->capacity = capacity
}
return capacity
}
//插入
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
TSeqList * sList = (TSeqList*)list
int i,ret = -1
if((sList != NULL) &&(pos >= 0) &&sList->capacity >= sList->len+1)
{
if(pos >= sList->len)
{
pos = sList->len
}
for(i = sList->leni >posi--)
{
sList->node[i] = sList->node[i-1]
}
sList->node[i] = (TSeqListNode)node
++sList->len
ret = 1
}
return ret
}
//获得指定位置的节点
SeqListNode* SeqList_Get(SeqList* list, int pos)
{
TSeqList * sList = (TSeqList*)list
TSeqListNode* node = NULL
if(NULL != sList &&pos>=0 &&pos <sList->len)
{
node = (TSeqListNode*)sList->node[pos]
}
return node
}
//删除
SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
TSeqList * sList = (TSeqList*)list
SeqListNode * node = SeqList_Get( list, pos)
int i
if(sList != NULL &&pos >= 0 &&pos<sList->len)
{
for( i=pos+1i<sList->leni++)
{
sList->node[i-1] = sList->node[i]
}
sList->len--
}
return node
}
演示:
资料拓展:
线性表是最基本、最简单、也是最常用的一种数据结构。
线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。
我们说“线性”和“非线性”,只在逻辑层次上讨论,而不考虑存储层次,所以双向链表和循环链表依旧是线性表。
在数据结构逻辑层次上细分,线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”,可以自由的删除或添加结点。受限线性表主要包括栈和队列,受限表示对结点的操作受限制。
线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
#include <stdio.h>#include <stdlib.h>
#define MAXSIZE 100 /*线性表的最大长度*/
typedef int ElemType
//描述线性表
typedef struct {
ElemType data[MAXSIZE]
int length /*当前表的长度*/
}SeqList
//初始化线性表
SeqList *init_SeqList() {
SeqList *L = (SeqList *)malloc(sizeof(SeqList))
L->length = 0
return L
}
// 插入
void InsertList(SeqList *L,int i,ElemType e) {
int k
if(L->length == 0 || i == L->length) {
L->data[L->length] = e
++L->length
return
}
if (i < 1 || i > L->length) {
printf("The position is mistake!\n")
printf("插入数据%d失败。\n",e)
return
}
for(k = L->lengthk >= ik--)
L->data[k] = L->data[k - 1]/* 结点移动 */
L->data[i - 1] = e
L->length++
}
//删除元素
int sqListDelete(SeqList *L,int i) { //???????
int k
if(i < 1 || i >= L->length) { /*检查删除位置的合法性*/
printf ("The position is mistake!")
return 0
}
for(k = i - 1k < L->lengthk++)
L->data[k] = L->data[k+1] /*向前移动*/
L->length--
return i
}
//
int SqlistLcate(SeqList *L,ElemType x) { //??????
int i
for(i = 0i < L->lengthi++) {
if(L->data[i] == x)
return i + 1 /*返回的是存储位置*/
}
return -1
}
void Show(SeqList *list) {
for(int i = 0 i < list->length++i)
printf("%d ",list->data[i])
printf("\n")
}
//主函数
int main() {
int x,loc
int i
SeqList *list = init_SeqList()
//添加10个数字给线性表list
printf("please input 10 numbers:")
for(i = 0 i < 10 i++) {
scanf("%d",&x)
InsertList(list,i,x)
}
Show(list)
printf("在第2个位置插入一个元素999后\n")
InsertList(list,2,999)
Show(list)
printf("删除元素%d后。\n",list->data[5 - 1])
sqListDelete(list,5)
Show(list)
//查找
loc = SqlistLcate(list,4)
if(loc >= 0) printf("第4个元素是:%d\n",list->data[loc])
else printf("没有找到第4个元素。\n")
return 0
}