編譯一個程序來構建一個線性表

1. 一個線性表的編程

//花了一個晚上和這個中午的時間，終於做好了，可以再VC 6.0里正確運行，基本可以到達你的要求，代碼：#include<iostream.h>
typedef int datatype; //線性表結點的數據類型，假設是 int
const int maxsize=100; //線性表可能的最大長度，這里假設是 100；
typedef struct{
datatype data[maxsize+1]; // 定義線性表的數據
int n; //線性表的長度
}sqlist;//建表
sqlist* creat()
{
datatype x;
int i=1;
sqlist *L;
L=new sqlist;
while(cin>>x,x!=0)
{
L->data[i]=x;
i++;
}
L->n=i-1;
L->data[0]=L->n;
return L;
}//插入函數
int insert(sqlist *L,datatype x,int i) { //將 x 插入到順序表 L得到第 i 個位置
int j;
if(L->n==maxsize) { cout<<"表滿，不能插入!(上溢)\n"; return -1; }
if(i<1 || i>L->n+1) {cout<<"非法插入位置!\n"; return 0; }
L->n++;
for(j=L->n;j>i;j--)
L->data[j]=L->data[j-1]; //結點後移
L->data[i]=x;
return 1;
}//刪除函數
int deletex(sqlist *L,datatype x) {
if(L->n==0) { cout<<"表空，不能刪除!(下溢)\n"; return 0;}
for(int j=1;j<=L->n;j++)
if(L->data[j]==x) //查找 匹配值 x
for(;j<=L->n;j++)
L->data[j]=L->data[j+1]; //結點前移
L->n--;
return 1;
}

//顯示順序表
void disp(sqlist *L)
{
cout<<"順序表的表長為 "<<L->n<<"\n 數據:\n";
for(int i=1;i<=L->n;i++)
cout<<"序號: "<<i<<" 數據: "<<L->data[i]<<endl;
}
void main()
{
sqlist *L=NULL;
datatype x;
int ch,i;
XX: while(1)
{
cout<<" 主菜單 \n "
<<" 0.退出\n "
<<" 1.建立順序表\n "
<<" 2.插入數據\n "
<<" 3.刪除數據\n "
<<" 4.顯示順序表\n ";
cin>>ch;
switch(ch)
{
case 0:
delete(L); //退出程序，撤銷順序表
return;
break;
case 1:
cout<<"請輸入順序表的數據(輸入 0 退出!)"<<endl;
L=creat();
cout<<"順序表已建成!\n";
break;
case 2:
cout<<"請輸入您要插入的值\n";
cin>>x;
cout<<"插入的位置:\n";
cin>>i;
if( insert(L,x,i)==1 ) cout<<"插入成功!"<<endl;
else cout<<"插入失敗! "<<endl;
break;
case 3:
cout<<"請輸入您要刪除的值\n";
cin>>x;
if(deletex(L,x)==1) cout<<"成功刪除數據 "<<x<<endl;
else cout<<"該順序表沒有數據 "<<x<<endl;
break;
case 4:
disp(L);
break;
default:
cout<<" 輸入非法! 請輸入 0~4選項!"<<endl;
goto XX;

}
}
}
//如果，還有什麼問題，歡迎追問！.^_^.

2. 作業要求： 用c語言編寫一個完整的程序，功能如下： 1，創建一個線性表，採用順序存儲的方式，鍵盤輸入初

#include <stdio.h>
#include <malloc.h>
#define NULL 0
struct link{
int num;
struct link *next;
};

struct link *creat(void)
{struct link *p1,*p2,*head;
p1=(struct link *)malloc(sizeof(struct link));
scanf("%d",&p1->num);
head=p1;
while(p1->num!=0)//這里一定要以數字0結束，而不能設置成#，因為num是整型。
{
p2=(struct link *)malloc(sizeof(struct link));
scanf("%d",&p2->num);
p1->next=p2;
p1=p2;
}
p1->next=NULL;
return head;
}

void print(struct link *head)
{struct link *p;
printf("\n結果是：\n");
p=head;
//這里不能加p=p->next;因為 p=head;已經是相當是p==head了，不能用誰指向誰來理解
while(p!=NULL)
{
printf("%d",p->num);
printf("\n");
p=p->next;
}
}

struct link *delet(struct link *head,int i)//有問題
{
struct link *p,*q;
int j=0;
p=head;

if(i==1)
{
p=p->next;
head=p;

}
else
{
while(p->next && j<(i-2))
{
p=p->next;
++j;
}
if(!(p->next) || j>i-2)
printf("刪除位置不合理");
q=p->next;
p->next=q->next;
free(q);
}

return head;
}

void main()
{
struct link *head1,*head2;
int i;
head1=creat();
print(head1);
printf("\n你要刪除第幾個數據：\n");
scanf("%d",&i);
head2=delet(head1,i);/*這里一定要用head2與前面的head1區分對待，否則如果如果鏈表並無改變
而僅僅是頭指針指向了第二個結點，那麼實際上也是從第一個結點開始輸出*/
printf("\n刪除後的結果是：\n");
print(head2);
}

3. 求構建一個線性表的完整程序 數據結構C語言版

#include "stdafx.h"
#define maxSize 100
typedef int elemType;
#include <stdio.h>
#include <stdlib.h>
typedef int elemType;
struct SeqList {
elemType *list;
int size;
int LmaxSize;
};

/* 初始化線性表L，即進行動態存儲空間分配並置L為一個空表 */
void initList(struct SeqList *L, int ms)
{
/* 檢查ms是否有效，若無效的則退出運行 */
if(ms <= 0){
printf("MaxSize非法！");
exit(1); /* 執行此函數中止程序運行，此函數在stdlib.h中有定義 */
}
L->LmaxSize = ms; /* 設置線性表空間大小為ms */
L->size = 0;
L->list = (int *)malloc(ms * sizeof(elemType));
if(!L->list){
printf("空間分配失敗！");
exit(1);
}
return;
}

/* 空間擴展為原來的2倍，並由p指針所指向，原內容被自動拷貝到p所指向的存儲空間 */
void againMalloc(struct SeqList *L)
{
elemType *p = (int *)realloc(L->list, 2 * L->LmaxSize * sizeof(elemType));
if(!p){ /* 分配失敗則退出運行 */
printf("存儲空間分配失敗！ ");
exit(1);
}
L->list = p; /* 使list指向新線性表空間 */
L->LmaxSize = 2 * L->LmaxSize; /* 把線性表空間大小修改為新的長度 */
}

/* 清除線性表L中的所有元素，釋放存儲空間，使之成為一個空表 */
void clearList(struct SeqList *L)
{
if(L->list != NULL){
free(L->list);
L->list = NULL;
L->size = L->LmaxSize = 0;
}
return;
}
/* 返回線性表L當前的長度，若L為空則返回0 */
int sizeList(struct SeqList *L)
{
return L->size;
}

/* 判斷線性表L是否為空，若為空則返回1, 否則返回0 */
int emptyList(struct SeqList *L)
{
if(L->size ==0){
return 1;
}
else{
return 0 ;
}
}

/* 返回線性表L中第pos個元素的值，若pos超出范圍，則停止程序運行 */
elemType getElem(struct SeqList *L, int pos)
{
if(pos < 1 || pos > L->size){ /* 若pos越界則退出運行 */
printf("元素序號越界！");
exit(1);
}
return L->list[pos - 1]; /* 返回線性表中序號為pos值的元素值 */
}

/* 順序掃描（即遍歷）輸出線性表L中的每個元素 */
void traverseList(struct SeqList *L)
{
int i;
for(i = 0; i < L->size; i++){
printf("%d ", L ->list[i]);
printf(" ");
}
return;
}

/* 從線性表L中查找值與x相等的元素，若查找成功則返回其位置，否則返回-1 */
int search(struct SeqList *L, elemType x)
{
int i;
for(i = 0; i < L->size; i++){
if(L->list[i] == x){
return i;
}
}
return -1;
}
/* 把線性表L中第pos個元素的值修改為x的值，若修改成功返回1，否則返回0 */
int updatePosList(struct SeqList *L, int pos, elemType x)
{
if(pos < 1 || pos > L->size){ /* 若pos越界則修改失敗 */
return 0;
}
L->list[pos - 1] = x;
return 1;
}

/* 向線性表L的表頭插入元素x */
void inserFirstList(struct SeqList *L, elemType x)
{
int i;
if(L->size== L->LmaxSize){ /* 重新分配更大的存儲空間 */
againMalloc(L);
}
for(i = L->size - 1; i >= 0; i--)/*元素後移*/
L->list[i + 1] = L ->list[i];
L->list[0] = x;
L->size ++;
}

/* 向線性表L的表尾插入元素x */
void insertLastList(struct SeqList *L, elemType x)
{
if(L->size == L ->LmaxSize){ /* 重新分配更大的存儲空間 */
againMalloc(L);
}
L->list[L->size] = x; /* 把x插入到表尾 */
L->size++; /* 線性表的長度增加1 */
return;
}

/* 向線性表L中第pos個元素位置插入元素x，若插入成功返回1，否則返回0 */
int insertPosList(struct SeqList *L, int pos, elemType x)
{
int i;
if(pos < 1 || pos > L->size + 1){ /* 若pos越界則插入失敗 */
return 0;
}
if(L->size == L->LmaxSize){ /* 重新分配更大的存儲空間 */
againMalloc(L);
}
for(i = L->size - 1; i >= pos - 1; i--){
L->list[i + 1] = L->list[i];
}
L->list[pos - 1] = x;
L->size++;
return 1;
}

/* 向有序線性表L中插入元素x,使得插入後仍然有序*/
void insertOrderList(struct SeqList *L, elemType x)
{
int i, j;
/* 若數組空間用完則重新分配更大的存儲空間 */
if(L->size == L->LmaxSize){
againMalloc(L);
}
/* 順序查找出x的插入位置 */
for(i = 0; i < L->size; i++){
if(x < L->list[i]){
break;
}
}
/* 從表尾到下標i元素依次後移一個位置， 把i的位置空出來 */
for(j = L->size - 1; j >= i; j--)
L->list[j+1] = L->list[j];
/* 把x值賦給下標為i的元素 */
L->list[i] = x;
/* 線性表長度增加1 */
L->size++;
return;
}
/* 從線性表L中刪除表頭元素並返回它，若刪除失敗則停止程序運行 */
elemType deleteFirstList(struct SeqList *L)
{
elemType temp;
int i;
if(L ->size == 0){
printf("線性表為空，不能進行刪除操作！ ");
exit(1);
}
temp = L->list[0];
for(i = 1; i < L->size; i++) /* 元素前移 */
L->list[i-1] = L->list[i];
L->size--;
return temp;
}

/* 從線性表L中刪除表尾元素並返回它，若刪除失敗則停止程序運行 */
elemType deleteLastList(struct SeqList *L)
{
if(L ->size == 0){
printf("線性表為空，不能進行刪除操作！ ");
exit(1);
}
L->size--;
return L ->list[L->size]; /* 返回原來表尾元素的值 */
}

/* 從線性表L中刪除第pos個元素並返回它，若刪除失敗則停止程序運行 */
elemType deletePosList(struct SeqList *L, int pos)
{
elemType temp;
int i;
if(pos < 1 || pos > L->size){ /* pos越界則刪除失敗 */
printf("pos值越界，不能進行刪除操作！ ");
exit(1);
}
temp = L->list[pos-1];
for(i = pos; i < L->size; i++)
L->list[i-1] = L->list[i];
L->size--;
return temp;
}

/* 從線性表L中刪除值為x的第一個元素，若成功返回1，失敗返回0 */
int deleteValueList(struct SeqList *L, elemType x)
{
int i, j;
/* 從線性表中順序查找出值為x的第一個元素 */
for(i = 0; i < L->size; i++){
if(L->list[i] == x){
break;
}
}
/* 若查找失敗，表明不存在值為x的元素，返回0 */
if(i == L->size){
return 0;
}
/* 刪除值為x的元素L->list[i] */
for(j = i + 1; j < L->size; j++){
L->list[j-1] = L->list[j];
}
L->size--;
return 1;
}

int main(int argc, char* argv[])
{

struct SeqList * ListPerson;
int Listsize=10;
int i;
int num;

ListPerson=(SeqList*)malloc(sizeof(SeqList)); //這句話很重要
initList(ListPerson,Listsize);

for (i=0;i<10;i++)
{
inserFirstList(ListPerson, i);
}

for (i=0;i<5;i++)
{
inserFirstList(ListPerson, i);
}

num=sizeList(ListPerson);

for (i=0;i<num;i++)
{
printf(" %d ", ListPerson->list[i]);
}

printf("\n");
insertPosList(ListPerson, 5, 100);

num=sizeList(ListPerson);

for (i=0;i<num;i++)
{
printf(" %d ", ListPerson->list[i]);
}

return 0;

}

4. 用C語言編寫程序實現線性表的順序存儲結構並實現以下功能： 1. 輸入一組整數構造線性表；

比如你要在第i個元素之後插入，就把i+1直到最後一個元素依次向後移動一位，再把你要放的元素放到第i+1位置即可

5. 求一個c++的建立線性表最簡單的程序，要能運行的

#include<malloc.h> // malloc()等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()

// 函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
typedef int ElemType;

#define LIST_INIT_SIZE 10 // 線性表存儲空間的初始分配量
#define LISTINCREMENT 2 // 線性表存儲空間的分配增量

線中間就是線性表的定義和函數。

————————————————————————————————————
struct SqList
{
ElemType *elem; // 存儲空間基址
int length; // 當前長度
int listsize; // 當前分配的存儲容量(以sizeof(ElemType)為單位)
};

Status InitList(SqList &L) // 演算法2.3
{ // 操作結果：構造一個空的順序線性表
L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (!L.elem)
exit(OVERFLOW); // 存儲分配失敗
L.length = 0; // 空表長度為0
L.listsize = LIST_INIT_SIZE; // 初始存儲容量
return OK;
}

Status DestroyList(SqList &L)
{ // 初始條件：順序線性表L已存在。操作結果：銷毀順序線性表L
free(L.elem);
L.elem = NULL;
L.length = 0;
L.listsize = 0;
return OK;
}

Status ClearList(SqList &L)
{ // 初始條件：順序線性表L已存在。操作結果：將L重置為空表
L.length = 0;
return OK;
}

Status ListEmpty(SqList L)
{ // 初始條件：順序線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE
if (L.length == 0)
return TRUE;
else
return FALSE;
}

int ListLength(SqList L)
{ // 初始條件：順序線性表L已存在。操作結果：返回L中數據元素個數
return L.length;
}

Status GetElem(SqList L, int i, ElemType &e)
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)
// 操作結果：用e返回L中第i個數據元素的值
if (i<1 || i>L.length)
exit(ERROR);
e = *(L.elem + i - 1);
return OK;
}

int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
{ // 初始條件：順序線性表L已存在，compare()是數據元素判定函數(滿足為1,否則為0)
// 操作結果：返回L中第1個與e滿足關系compare()的數據元素的位序。
// 若這樣的數據元素不存在，則返回值為0。演算法2.6
ElemType *p;
int i = 1; // i的初值為第1個元素的位序
p = L.elem; // p的初值為第1個元素的存儲位置
while (i <= L.length&&!compare(*p++, e))
++i;
if (i <= L.length)
return i;
else
return 0;
}

Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e)
{ // 初始條件：順序線性表L已存在
// 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅，
// 否則操作失敗，pre_e無定義
int i = 2;
ElemType *p = L.elem + 1;
while (i <= L.length&&*p != cur_e)
{
p++;
i++;
}
if (i>L.length)
return INFEASIBLE;
else
{
pre_e = *--p;
return OK;
}
}

Status NextElem(SqList L, ElemType cur_e, ElemType &next_e)
{ // 初始條件：順序線性表L已存在
// 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼，
// 否則操作失敗，next_e無定義
int i = 1;
ElemType *p = L.elem;
while (i<L.length&&*p != cur_e)
{
i++;
p++;
}
if (i == L.length)
return INFEASIBLE;
else
{
next_e = *++p;
return OK;
}
}

Status ListInsert(SqList &L, int i, ElemType e) // 演算法2.4
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)+1
// 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1
ElemType *newbase, *q, *p;
if (i<1 || i>L.length + 1) // i值不合法
return ERROR;
if (L.length >= L.listsize) // 當前存儲空間已滿,增加分配
{
if (!(newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType))))
exit(OVERFLOW); // 存儲分配失敗
L.elem = newbase; // 新基址
L.listsize += LISTINCREMENT; // 增加存儲容量
}
q = L.elem + i - 1; // q為插入位置
for (p = L.elem + L.length - 1; p >= q; --p) // 插入位置及之後的元素右移
*(p + 1) = *p;
*q = e; // 插入e
++L.length; // 表長增1
return OK;
}

Status ListDelete(SqList &L, int i, ElemType &e) // 演算法2.5
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)
// 操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1
ElemType *p, *q;
if (i<1 || i>L.length) // i值不合法
return ERROR;
p = L.elem + i - 1; // p為被刪除元素的位置
e = *p; // 被刪除元素的值賦給e
q = L.elem + L.length - 1; // 表尾元素的位置
for (++p; p <= q; ++p) // 被刪除元素之後的元素左移
*(p - 1) = *p;
L.length--; // 表長減1
return OK;
}

Status ListTraverse(SqList L, void(*vi)(ElemType&))
{ // 初始條件：順序線性表L已存在
// 操作結果：依次對L的每個數據元素調用函數vi()。一旦vi()失敗，則操作失敗
// vi()的形參加'&'，表明可通過調用vi()改變元素的值
ElemType *p;
int i;
p = L.elem;
for (i = 1; i <= L.length; i++)
vi(*p++);
printf("\n");
return OK;
}
————————————————————————————————————

void print(ElemType &c)
{
printf("%d ", c);
}

void main()
{
SqList La;
int j;
InitList(La);
for (j = 1; j <= 5; j++) // 在表La中插入5個元素
ListInsert(La, j, j);
printf("La= "); // 輸出表La的內容
ListTraverse(La, print);
}

6. 如何用c++建立一個線性表

用c++建立一個線性表有以下5步：

1、准備數據：

7. 怎麼構造一個空的線性表

構造一個空的線性表，就是對SqList線性表類型的三個分量elem、listsize和length賦初值的過程。

1.操作步驟（1）申請一片連續的存儲空間，並把其地址空間賦給elem指針變數。

（2）開始時length的初值為0。

（2）對listsize賦初值，其值是申請函數申請空間的最大容量。

2）構造空線性表的演算法2）把構造空線性表的演算法改成程序演算法與程序不同，為幫助初學者理解兩者的區別，把演算法2.1轉化成程序的操作步驟如下：

（1）添加C程序用的頭文件和宏定義：（2）線性表類型定義：（2）構造空線性表的函數定義。

為了便於對線性表以後的操作，L可被定義成全局變數，若把演算法2.1改成程序，需要增加對線性表賦值和輸出的語句。（4）記住一定要加主函數：

圖1演算法2.1

8. 用c語言編寫程序1.建立一個線性表，輸入n個元素並輸出2.查找最大元素並輸出

線性表 可以使用鏈表 或者數組實現

以動態數組為例

#include<stdio.h>
#include<stdlib.h>
intmain()
{
int*a,n,max,i;
scanf("%d",&n);
a=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
scanf("%d",a+i);
for(i=1,max=a[0];i<n;i++)
if(max<a[i])max=a[i];
printf("%d
",max);
free(a);
return0;
}