データ構造でーたこうぞう:シーケンシャルテーブルシーケンシャルテーブル
/*
* this c file is a implementation of linear list
* author: John Woods
* date: 2015/5/3
* exclaim: anyone can use the file to any purpose
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define INIT_LEN 20
#define INCREMENT_SIZE 10
#define BOOL int /* define boolean type */
#define TRUE 1
#define FALSE 0
/* linear list structure */
typedef struct LinearList {
int * LL;
int Length;
int MaxLength;
} * LinearList;
/* menu */
void menu();
void insert(LinearList myLL);
void delete(LinearList myLL);
void prior(LinearList myLL);
void next(LinearList myLL);
void current(LinearList myLL);
/* operations */
LinearList initList(); /* initial the linear list */
void destroyList(LinearList * p_myLL); /* destroy the linear list, the linear list must be exist */
void clearList(LinearList myLL); /* clear the linear list, the linear list must be exist */
BOOL listEmpty(LinearList myLL); /* if linear list is empty, return TRUE, else return FALSE, and the linear list must be exist */
BOOL getElem(LinearList myLL, int index, int * cur_e); /* return the value of list[i] in e, the linear list must be exist and i must between 0 and list.length-1 */
BOOL priorElem(LinearList myLLL, int index, int * pre_e); /* return the prior element of the list[i], the linear list must be exist */
BOOL nextElem(LinearList myLL, int index, int * next_e); /* return the next element of the list[i], the linear list must be exist */
void listInsert(LinearList myLL, int index, int e); /* insert a element of e int position of i, the linear list must be exist and the i must between 0 and list.length */
BOOL listDelete(LinearList myLL, int index, int * e); /* delete the element in position i, and return its value in e, the linear list must be exist */
void listTraverse(LinearList myLL); /* traverse the list with the function visit() */
BOOL listExist(LinearList myLL);
void myflush();
int main(void) {
int instruct = 0;
LinearList myLL = NULL;
while(TRUE) {
menu();
while(!scanf("%d", &instruct));
switch(instruct) {
case 1:
myLL = initList();
myLL->Length = 0;
myLL->MaxLength = INIT_LEN;
break;
case 2:
listTraverse(myLL);
break;
case 3:
insert(myLL);
break;
case 4:
delete(myLL);
break;
case 5:
prior(myLL);
break;
case 6:
next(myLL);
break;
case 7:
current(myLL);
break;
case 8:
clearList(myLL);
break;
case 9:
destroyList(&myLL);
break;
default:
exit(EXIT_SUCCESS);
break;
}
}
return 0;
}
void menu() {
printf("Please choose your operation:
");
printf("\t| 1.initial a linear list 2.traverse the list
");
printf("\t| 3.insert an element 4.delete an element
");
printf("\t| 5.get the prior element 6.get the next element
");
printf("\t| 7.get an element 8.clear the linear list
");
printf("\t| 9.destroy the linear list 0.exit
");
printf("Give me your choice:");
}
void insert(LinearList myLL) {
int index, e;
char c,GoOn;
if(FALSE == listExist(myLL)) {
printf("Please initial the linear list first!
");
return;
}
while(TRUE)
{
//while('
'!=(c=getchar()) && EOF!=c); //clear the stdin stream
printf("Input the insert position:");
while(!scanf("%d", &index));
while('
'!=(c=getchar()) && EOF!=c); //clear the stdin stream
printf("Input the insert value:");
while(!scanf("%d", &e));
listInsert(myLL, index, e);
while('
'!=(c=getchar()) && EOF!=c); //clear the stdin stream
printf("Go on?(y/n) ");
GoOn = getchar();
if(GoOn != 'y' && GoOn != 'Y' && GoOn != '
') break;
}
}
void delete(LinearList myLL) {
int index, e;
char c, GoOn;
if(FALSE == listExist(myLL)) {
printf("Please initial the linear list first!
");
return;
}
while(TRUE) {
while('
'!=(c=getchar()) && EOF!=c); //clear the stdin stream
printf("Please input the index for delete: ");
scanf("%d", &index);
if(listDelete(myLL, index, &e)) {
printf("The deleted value is %d
", e);
}
while('
'!=(c=getchar()) && EOF!=c); //clear the stdin stream
printf("Go on?(y/n) ");
GoOn = getchar();
if(GoOn != 'y' && GoOn != 'Y' && GoOn != '
') break;
}
}
void prior(LinearList myLL) {
int index, pre_e;
char c;
if(FALSE == listExist(myLL)) {
printf("Please initial the linear list first!
");
return;
}
while('
'!=(c=getchar()) && EOF!=c); //clear the stdin stream
printf("Please input the index: ");
scanf("%d", &index);
if(priorElem(myLL, index, &pre_e)) {
printf("The value before position %d is %d
", index, pre_e);
}
}
void next(LinearList myLL) {
int index, next_e;
char c;
if(FALSE == listExist(myLL)) {
printf("Please initial the linear list first!
");
return;
}
while('
'!=(c=getchar()) && EOF!=c); //clear the stdin stream
printf("Please input the index: ");
scanf("%d", &index);
if(nextElem(myLL, index, &next_e)) {
printf("The value after position %d is %d
", index, next_e);
}
}
void current(LinearList myLL) {
int index, cur_e;
char c;
if(FALSE == listExist(myLL)) {
printf("Please initial the linear list first!
");
return;
}
while('
'!=(c=getchar()) && EOF!=c); //clear the stdin stream
printf("Please input the index: ");
scanf("%d", &index);
if(getElem(myLL, index, &cur_e)) {
printf("The value in position %d is %d", index, cur_e);
}
}
LinearList initList() {
LinearList myLL = (LinearList)malloc(sizeof(struct LinearList));
if(NULL == myLL) {
printf("ERROR:Out of memeory
");
exit(EXIT_FAILURE);
}
myLL->LL = (int *)malloc(sizeof(int) * INIT_LEN);
if(NULL == myLL->LL) {
printf("ERROR:Out of memory
");
exit(EXIT_FAILURE);
}
printf("The linear list has been initialized
");
return myLL;
}
void destroyList(LinearList * p_myLL) {
if(FALSE == listExist(*p_myLL)) {
printf("Please initial the linear list first!
");
return;
}
free((*p_myLL)->LL);
(*p_myLL)->LL = NULL;
free(*p_myLL);
*p_myLL = NULL;
printf("The list has been destroyed!
");
}
void clearList(LinearList myLL) {
if(FALSE == listExist(myLL)) {
printf("Please initial the linear list first!
");
return;
}
if(FALSE == listEmpty(myLL)) {
myLL->Length = 0;
printf("Clear operation is successful!
");
}
}
BOOL listEmpty(LinearList myLL) {
if(0 == myLL->Length) {
return TRUE;
}else {
return FALSE;
}
}
BOOL getElem(LinearList myLL, int index, int * cur_e) {
if(index <= myLL->Length && index >= 1) {
*cur_e = *(myLL->LL + index - 1);
return TRUE;
}else {
printf("You got wrong index!
");
return FALSE;
}
}
BOOL priorElem(LinearList myLL, int index, int * pre_e) {
if(index > myLL->Length || index <= 1) {
printf("You got wrong index!
");
return FALSE;
}else {
*pre_e = *(myLL->LL + index - 2);
return TRUE;
}
}
BOOL nextElem(LinearList myLL, int index, int * next_e) {
if(index >= myLL->Length || index <1) {
printf("You got wrong index!
");
return FALSE;
}else {
*next_e = *(myLL->LL + index);
return TRUE;
}
}
void listInsert(LinearList myLL, int index, int e) {
int i;
if((myLL->Length+1)>myLL->MaxLength) {
myLL->LL = (int *)realloc(myLL->LL,sizeof(int) * (myLL->MaxLength + INCREMENT_SIZE));
myLL->MaxLength += INCREMENT_SIZE;
}
if(index > myLL->Length+1 || index<1) {
printf("You got wrong position!
");
return;
}else {
for(i=myLL->Length-1; i>=index-1; i--) {
*(myLL->LL + i + 1) = *(myLL->LL + i);
}
*(myLL->LL + index - 1) = e;
myLL->Length++;
printf("Insert operation is successful!
");
}
}
BOOL listDelete(LinearList myLL, int index, int * e) {
int i;
if(index > myLL->Length || index < 1) {
printf("You got wrong index!
");
return FALSE;
}else {
*e = *(myLL->LL + i - 1);
for(i = index-1; i < myLL->Length-1; i++) {
*(myLL->LL + i) = *(myLL->LL + i + 1);
}
myLL->Length--;
printf("Delete operation is successful!
");
return TRUE;
}
}
void listTraverse(LinearList myLL) {
int i;
if(FALSE == listExist(myLL)) {
printf("Please initial the linear list first!
");
return;
}
printf("Length of the linear list is %d
", myLL->Length);
printf("Its elements are following:
\t");
printf("HEAD->");
for(i=0; i<myLL->Length; i++) {
printf("%d->", *(myLL->LL + i));
}
printf("END
");
}
BOOL listExist(LinearList myLL) {
if(NULL == myLL) return FALSE;
else return TRUE;
}コードはubuntu環境で書かれているからです!実装中、fflush(stdin)で入力バッファを空にすることができないことがわかりました.資料を見ると、fflush()は標準ライブラリ関数ではなく、その動作は定義されていません.
fflush(stdin); /* ， ， */
while('
'!=(c=getchar()) && EOF!=c); /* */